定义

在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。


正文

半年前学的内容了没想到现在还是不会

带环的图中不能进行拓扑排序!!!

大致操作是这样:


0.读入数据

1.找到所有入度为$0$的点,并放入队列

2.不断取出队列中的点,把所有他连向的点的入度减去一,并且判断是否应该加入队列,直到队列为空


这样操作完成之后,点进入队列的先后顺序即为所求的序列。

注意事项:

1.因为进入队列的都是入度为$0$的点,所以一个点不会第二次被拓展进入队列。所以假设存在拓扑序列,一定是每个点都加入了队列一次,如果数据对不上的话就说明这个图中含有环,不能进行拓扑排序。

2.如果在同一时间队列中存在$2$个及以上的元素,说明这个图中的拓扑序列不唯一。

3.如果需要拓扑序列字典序最小,就把队列换成优先队列就好了。


最后修改:2020 年 04 月 10 日 06 : 15 PM