734 Status TopoSeq( ALGraph G, int new]∥/按照题目要求给有向无环图的结点重新编 号并存入数组new中 int indegreeIMAXSIZE]∥本算法就是拓扑排序 FindIndegree(G, indegree) Initstack(S) for(i=0; K<G. vexnum; i++) if(indegree)Push(S, 1); while(lstackempty(s)) Pop(S)new[}=+ -count,∥把拓扑顺序存入数组的对应分量中 for(p=G vertices[]. firstarc p p=p->nextarc) k if(!(--indegree[])) Push(S, k) i//while if(count<G. vexnum) return ERROR eturn OK. 735 int visited MAXSIZE] void get root( ALGraph G求有向无环图的根如果有的话 for( v=0; V<G. vexnum; v++) for(w=0,w< G. vexnum,w++) visited w}=0∥每次都要将访问数组清零 DFS(G,V),∥从顶点v出发进行深度优先遍历 for(flag=1, w=0; w<G. vexnum; w++) if(visited w])fag=0;∥如果ⅴ是根,则深度优先遍历可以访问到所有结点 if(flag) printf("Found a root vertex: %d n" V); ∥for }/ Get root,这个算法要求图中不能有环否则会发生误判 void DFS(ALGraph G, int v) visited]=1 for(p=G vertices[v]. firstarc: pp=p->nextarc)7.34 Status TopoSeq(ALGraph G,int new[ ])//按照题目要求给有向无环图的结点重新编 号,并存入数组 new 中 { int indegree[MAXSIZE]; //本算法就是拓扑排序 FindIndegree(G,indegree); Initstack(S); for(i=0;i<G.vexnum;i++) if(!indegree[i]) Push(S,i); count=0; while(!stackempty(S)) { Pop(S,i);new[i]=++count; //把拓扑顺序存入数组的对应分量中 for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!(--indegree[k])) Push(S,k); } }//while if(count<G.vexnum) return ERROR; return OK; }//TopoSeq 7.35 int visited[MAXSIZE]; void Get_Root(ALGraph G)//求有向无环图的根,如果有的话 { for(v=0;v<G.vexnum;v++) { for(w=0;w<G.vexnum;w++) visited[w]=0;//每次都要将访问数组清零 DFS(G,v); //从顶点 v 出发进行深度优先遍历 for(flag=1,w=0;w<G.vexnum;w++) if(!visited[w]) flag=0; //如果 v 是根,则深度优先遍历可以访问到所有结点 if(flag) printf("Found a root vertex:%d\n",v); }//for }//Get_Root,这个算法要求图中不能有环,否则会发生误判 void DFS(ALGraph G,int v) { visited[v]=1; for(p=G.vertices[v].firstarc;p;p=p->nextarc) {