visit(k) visited kF=1 Push(S, k); i//Traverse Nonrecursive 分析本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37由于 是强连通图所以从第一个结点出发一定能够访问到所有结点 725 见书后解答 7.2 Status TopoN( ALGraph G/按照题目要求顺序重排有向图中的顶点 int new MAXSIZE), indegree MAXSIZE]∥储存结点的新序号 FindInDegree(G, indegree); Init Stack(S) for(Fl; K<G. vexnum; i++) if(indegree[i])Push(S,i,∥零入度结点入栈 while(!Stack Empty(s) Pop(s, 1); Ni=n-;∥记录结点的拓扑逆序序号 count++ for(p=G vertices[i]. firstarc p p=p->nextarc) if(!(-indegreek]) Push(s, k); i//for i//while if(count< G. vexnum) return error;∥图中存在环 for(F1; K<=n; i++)printf("Old No: %d New No: %d\n", i, new[) eturn OK. M//TopoN 分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵 72 int visited MAXSIZe]visit(k); visited[k]=1; Push(S,k); } }//if }//while }//Straverse_Nonrecursive 分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考 6.37.由于 是强连通图,所以从第一个结点出发一定能够访问到所有结点. 7.25 见书后解答. 7.26 Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点 { int new[MAXSIZE],indegree[MAXSIZE]; //储存结点的新序号 n=G.vexnum; FindInDegree(G,indegree); InitStack(S); for(i=1;i<G.vexnum;i++) if(!indegree[i]) Push(S,i); //零入度结点入栈 count=0; while(!StackEmpty(S)) { Pop(S,i); new[i]=n--; //记录结点的拓扑逆序序号 count++; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!(--indegree[k])) Push(S,k); }//for }//while if(count<G.vexnum) return ERROR; //图中存在环 for(i=1;i<=n;i++) printf("Old No:%d New No:%d\n",i,new[i]) return OK; }//TopoNo 分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵. 7.27 int visited[MAXSIZE];