数据结构精品课件-拓扑排序算法.pptVIP

* 7.7 拓扑排序算法 第 7 章 图 如何进行拓扑排序？ Ⅰ.从有向图中选取一个没有前驱的顶点，并输出之； Ⅱ.从有向图中删去此顶点以及所有以它为尾的弧； 重复上述两步，直至图空，或者图不空 但找不到无前驱的顶点为止。 * 第 7 章 图 例如： C D A G F B H E C D A G F B H E A C B H D G F E 没有前驱的顶点 ?? 入度为零的顶点 删除顶点及它的出弧 ?? 弧头顶点的入度减1 7.7 拓扑排序算法 对于有向图的不同存储结构，拓扑排序算法的实现是不同的。 基于邻接矩阵表示的有向图拓扑排序方法如下： 设A为有向图G的邻接矩阵，则 （1）找G中无前驱的顶点 — 在A中找到值全为0的列； （2）删除以i为起点的所有弧 — 将矩阵中i对应的行全部置为0。 第 7 章 图 * 7.7 拓扑排序算法 1、没有前驱的顶点 ?? 入度为零的顶点 2、删除顶点及它的出弧 ?? 弧头顶点的入度-1 辅助数组记录各顶点的入度； 建栈记录入度为零的顶点； 基于邻接表表示的有向图拓扑排序方法如下： 第 7 章 图 * * 7.7 拓扑排序算法 a b c g h d f e b a b h c d g f e a c d g h f e 栈S: 1 0 a 3 7 2 0 b 7 8 3 1 c 4 4 1 d 5 7 5 2 e 6 2 f 5 7 3 g 6 8 1 h 6 2 1 1 0 0 1 0 0 0 0 * 拓扑排序算法 int TopoSort (AdjList G) {FindID(G,indegree); /*求各顶点入度*/ count=0; InitStack(S); for(i=0;iG.vexnum;i++) if(indegree[i]==0) Push(S,i); while(!StackEmpty(S)) { Pop(S,i); printf(%c,G.vertex[i].data); count++; p=G.vertexes[i].firstarc; while(p!=NULL) { k=p-adjvex; indegree[k]--; if(indegree[k]==0) Push(S, k); p=p-nextarc; } } if (countG.vexnum) return(Error); else return(Ok); } 时间复杂度为: O(n+e) 求各顶点入度的函数 void FindID( AdjList G, int indegree[MAX]) { int i; ArcNode *p; for(i=0; iG.vexnum; i++) indegree[i]=0; for(i=0; iG.vexnum; i++) { p=G.vertexes[i].firstarc; while(p!=NULL) { indegree[p-adjvex]++; p=p-nextarc; } } } *