intf("%d"yv),∥在第二次遍历中输出结点序号 for(p=G xlist[v].firstin, p; p=p->hlink) W-E if(visited w)DFS2(G, w); i//fo 3//DFS2 分析求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为 732 void forest prim( ALGraph G, int k, STRee&Ty∥从顶点k出发,构造邻接表结构的 有向图G的最小生成森林T用孩子兄弟链表存储 for(j=0 K<G. vexnum, j++)∥以下在Prim算法基础上稍作改动 ifgI=k) closedge](k, Max int) for(p=G vertices[]. firstarc pp=p->nextarc) if(p->adjvexk)closedgeL]lowcost=p->cost closedge[k]. lowcost=0; for(F1; K<G. vexnum; i++) k-minimum(closedge): if(closed ge[].lowcost<Max int) Addto forest( T, closedgek] adjvex, k),∥把这条边加入生成森林中 closedge[k]. lowcost=0 for(p=G vertices[k ]. firstarc: p: p=p->nextarc) if(p->cost<closedge[p->adjvex] lowcost) closedgelp->adjvex](k, p->cost) else forest prim(Gk,∥对另外一个连通分量执行算法 i//Forest Prim void addto forest( STRee& T, int i, int jν把边(ij)添加到孩子兄弟链表表示的树T 中 p=Locate(I,i;∥找到结点i对应的指针p过程略 F(CSTNode*)malloc(sizeof(CS TNode)) if!tp)/起始顶点不属于森林中已有的任何一棵树printf("%d",v); //在第二次遍历中输出结点序号 for(p=G.xlist[v].firstin;p;p=p->hlink) { w=p->tailvex; if(!visited[w]) DFS2(G,w); }//for }//DFS2 分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为 O(n+e). 7.32 void Forest_Prim(ALGraph G,int k,CSTree &T)//从顶点 k 出发,构造邻接表结构的 有向图 G 的最小生成森林 T,用孩子兄弟链表存储 { for(j=0;j<G.vexnum;j++) //以下在 Prim 算法基础上稍作改动 if(j!=k) { closedge[j]={k,Max_int}; for(p=G.vertices[j].firstarc;p;p=p->nextarc) if(p->adjvex==k) closedge[j].lowcost=p->cost; }//if closedge[k].lowcost=0; for(i=1;i<G.vexnum;i++) { k=minimum(closedge); if(closedge[k].lowcost<Max_int) { Addto_Forest(T,closedge[k].adjvex,k); //把这条边加入生成森林中 closedge[k].lowcost=0; for(p=G.vertices[k].firstarc;p;p=p->nextarc) if(p->cost<closedge[p->adjvex].lowcost) closedge[p->adjvex]={k,p->cost}; }//if else Forest_Prim(G,k); //对另外一个连通分量执行算法 }//for }//Forest_Prim void Addto_Forest(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树 T 中 { p=Locate(T,i); //找到结点 i 对应的指针 p,过程略 q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j; if(!p) //起始顶点不属于森林中已有的任何一棵树