p=(CSTNode* )malloc(sizeof(CSTNode)) p->data=1; for(rT; r ->nextsib rr->nextsib) p->firstchild=q }∥作为新树插入到最右侧 else if(p-> firstchild)/双亲还没有孩子 p> firstchild=q;∥作为双亲的第一个孩子 else∥双亲已经有了孩子 for(rp->firstchild; r ->nextsib r-r->nextsib) r-> nextsib=q,∥作为双亲最后一个孩子的兄弟 ∥ Addto forest main T=( CSTNode* malloc( sizeof( CSTNode);∥建立树根 Forest Prim(g, 1,T) 分析这个算法是在Pim算法的基础上添加了非连通图支持和孩子兄弟链表构建 模块而得到的,其时间复杂度为O(n^2) 733 ypedef struct int vex,/结点序号 int eco;,∥结点所属的连通分量号 }Ⅴ exInfo Vexlnfo vexs[MAXSIZE]∥记录结点所属连通分量号的数组 void Init VexInfo( VexInfo&vexs[], int vexnum )初始化 for(0; i<vexnum; i++ vexs[={i};∥初始状态:每一个结点都属于不同的连通分量 i//nit VexInfo int is ec( VexInfo vexs[l, Int 1, Int判断顶点i和顶点j是否属于同一个连通分量 if(vexs[].ecno==vexs[i). ecn) return I{ p=(CSTNode*)malloc(sizeof(CSTNode)); p->data=i; for(r=T;r->nextsib;r=r->nextsib); r->nextsib=p; p->firstchild=q; } //作为新树插入到最右侧 else if(!p->firstchild) //双亲还没有孩子 p->firstchild=q; //作为双亲的第一个孩子 else //双亲已经有了孩子 { for(r=p->firstchild;r->nextsib;r=r->nextsib); r->nextsib=q; //作为双亲最后一个孩子的兄弟 } }//Addto_Forest main() { ... T=(CSTNode*)malloc(sizeof(CSTNode)); //建立树根 T->data=1; Forest_Prim(G,1,T); ... }//main 分析:这个算法是在 Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建 模块而得到的,其时间复杂度为 O(n^2). 7.33 typedef struct { int vex; //结点序号 int ecno; //结点所属的连通分量号 } VexInfo; VexInfo vexs[MAXSIZE]; //记录结点所属连通分量号的数组 void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化 { for(i=0;i<vexnum;i++) vexs[i]={i,i}; //初始状态:每一个结点都属于不同的连通分量 }//Init_VexInfo int is_ec(VexInfo vexs[ ],int i,int j)//判断顶点 i 和顶点 j 是否属于同一个连通分量 { if(vexs[i].ecno==vexs[j].ecno) return 1;