图--拓扑排序

前言

今天上课刚好讲到了拓扑排序，感觉很有意思，加了一些自己的思考记录下来。

先从阐述一下定义

以这张图来讲解如何实现拓扑排序，首先 a ，b两个顶点是没有前驱的顶点的，所以说先用a（或b也一样）入栈，然后擦除 a 指出去的箭头（相当于独立出来了），然后再看剩下的没有前驱顶点的顶点，重复这个操作，直到图空。

大概流程图就是这样啦：

这个过程中会依靠到栈。

在算法中，需要以定量的描述来替代定性的概念，比如：

1）没有前驱的顶点：入度为0的顶点。

2）删除顶点以及以它为尾的弧：弧头顶点的入度减一。 

算法描述

取入度为零的顶点v;
while (v<>0) {            //当v非空printf(v);  ++m;w:=FirstAdj(v);      //求v的邻接点while (w<>0) {inDegree[w]--;w:=nextAdj(v,w); //求v的下一个邻接点}取下一个入度为零的顶点v;
}
if m<n  printf("图中有回路");

 刚刚有说到需要用到栈，那栈的作用体现在这里：

CountInDegree(G,indegree);  // 对各顶点求入度。
InitStack(S);
for ( i=0; i<G.vexnum; ++i)if (!indegree[i])  Push(S, i); // 入度为零的顶点入栈
count=0;                        // 对输出顶点计数
while (!EmptyStack(S)) {Pop(S, v); ++count; printf(v);for (w=FirstAdj(v); w;  w=NextAdj(G,v,w)){--indegree(w);            // 弧头顶点的入度减一if (!indegree[w])  Push(S, w);// 新产生的入度为零的顶点入栈}
}
if ( count<G.vexnum )printf("图中有回路");

是的，为了避免每次都要搜素入度为零的顶点，在算法中可以设置一个“栈”来存储“入度为0”的顶点。

好啦，今天的分享就到这里，希望大家也会体会到拓扑排序的有趣之处。