By Zhang, Cheng

更新日期:

文章目录
  1. 1. 求有向无圈图的拓扑序列
    1. 1.1. 问题的描述
    2. 1.2. 求解思路
    3. 1.3. 伪代码
    4. 1.4. 例子和复杂度分析

求有向无圈图的拓扑序列

问题的描述

拓扑序列表示一组图中节点的列表，序列中的每个节点必须满足这样的条件：如果边(s,t)在图中（s为源节点，t为汇节点），那么点s在序列中的位置在t位置之前。

根据上面的条件，我们可以得到这样2个结论：

  • 这个图必须得是有向无权图（DAG），不然s与t成为一个环，与条件矛盾；
  • 图的拓扑序列不唯一，可以有很多种序列结果；

拓扑序列在生活中也很常见，比如我们做事都会有个先后顺序，总得是先买菜，才能再洗菜和烧菜。在大学里选修课程也是如此，学习编译原理、软件工程这样的课程的前修课是计算机原理或者程序设计与分析。

求解思路

拓扑序列的第一个节点肯定是没有入度的，不然仍会有个点在它前面，与条件矛盾，那么我们可以从节点的入度进行考虑。在整个求拓扑序列的过程中，我们需要维护一个入度为0的列表。在图输入后，我们就可以得到图中所有节点的入度情况。找出入度为0的节点a，接着遍历他们指向的点bi，删除边(a,bi)并更新入度。如果入度变成0，表示刚刚删除的边是唯一指向bi的边，那么可以将bi加入到入度为0的节点集合中。

伪代码

上面讲了思路有点抽象，伪代码是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Topological_Sort(G，*inDegree)
Input: Graph G,  //图结构
	   *inDegree //记录各个节点的入度情况
	InDegreeZeroSet; //入度为0的节点集合
	topologicalSequence; //拓扑序列
	InDegreeZeroSet = Initiation(*inDegree); //得到未删边前的入度为0的集合
	foreach vertex in InDegreeZeroSet:
		Add vertex to topologicalSequence;
		remove vertex from InDegreeZeroSet;
		foreach ti in edge(vertex,ti):
			remove edge(vertex,ti);
			update *inDegree;
			if(inDegree[ti] == 0)
				Add ti to InDegreeZeroSet;
			End
		End
	End
	if(|edge|!=0)//删除所有边后仍然有边存在
		error output("No topological sort");
	else
		output topologicalSequence;

例子和复杂度分析

下面我们来举个例子，图是这样的：

得到的拓扑排序结果是：

2->8->0->3->7->1->5->6->9->4->11->10->12

最后进行算法复杂度分析：在获取最初的入度为0的点集时，需要对图中每个节点和边进行遍历（其实就是图的输入），所以这里的复杂度是O(V+E)。接着遍历入度为0的点集时，要删除所有的边来得到所有的节点，所以复杂度也是O(V+E)。故这个方法的复杂度是O(V+E)。

PS: 这里需要补充一下，实现图的数据结构不同，会导致复杂度也不同。如果是用邻接表来实现图的话，那么在对边的遍历需要花费O(E)，整个复杂度是O(V+E)；而如果用邻接矩阵来实现图的话，那么对边的遍历需要花费O(V^2)，整个复杂度就变成了O(V+V^2)=O(V^2)。这里就需要我们根据图的稠密情况来进行取舍了。

文章目录
  1. 1. 求有向无圈图的拓扑序列
    1. 1.1. 问题的描述
    2. 1.2. 求解思路
    3. 1.3. 伪代码
    4. 1.4. 例子和复杂度分析