定义
对于任何有向图而言，其拓扑排序为其所有结点的一个线性排序（对于同一个有向图而言可能存在多个这样的结点排序）。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。
举个简单的例子， 某校的选课系统规定，每门课可能有若干个先修课，如果要修读某一门课程，则必须要先修完所有的先修课才能修读。假设一个学生同时只能报一门课程，那么选课系统允许他修完所有课程的顺序就是一个拓扑序…
拓补排序存在的前提
当且仅当一个有向图为有向无环图（directed acyclic graph，或称DAG）时，才能得到对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。
算法思想
拓扑排序的问题存在一个线性时间解。也就是说，若有向图中存在n个结点，则我们可以在O(n)时间内得到其拓扑排序，或在O(n)时间内确定该图不是有向无环图，也就是说对应的拓扑排序不存在。
如上图有两个拓补排序结果：[1, 2, 3, 4, 5]和[1, 2, 3, 5, 4]。
为了说明如何得到一个有向无环图的拓扑排序，我们首先需要了解有向图结点的入度（indegree）和出度（outdegree）的概念。
入度和出度
- 入度：设有向图中有一结点v，其入度即为当前所有从其他结点出发，终点为v的的边的数目。也就是所有指向v的有向边的数目。
- 出度：设有向图中有一结点v，其出度即为当前所有起点为v，指向其他结点的边的数目。也就是所有由v发出的边的数目。
在了解了入度和出度的概念之后，再根据拓扑排序的定义，我们自然就能够得出结论：要想完成拓扑排序，我们每次都应当从入度为0的结点开始遍历。因为只有入度为0的结点才能够成为拓扑排序的起点。否则根据拓扑排序的定义，只要一个结点v的入度不为0，则至少有一条边起始于其他结点而指向v，那么这条边的起点在拓扑排序的顺序中应当位于v之前，则v不能成为当前遍历的起点。
由此我们可以进一步得出一个改进的深度优先遍历或广度优先遍历算法来完成拓扑排序。以广度优先遍历为例，这一改进后的算法与普通的广度优先遍历唯一的区别在于我们应当保存每一个结点对应的入度，并在遍历的每一层选取入度为0的结点开始遍历（而普通的广度优先遍历则无此限制，可以从队列中任意一个结点开始遍历）。
算法步骤
- 初始化一个int[] inDegree保存每一个结点的入度。
- 对于图中的每一个结点的子结点，将其子结点的入度加1。
- 选取入度为0的结点开始遍历，并将该节点加入输出。
- 对于遍历过的每个结点，更新其子结点的入度：将子结点的入度减1。
- 重复步骤3，直到遍历完所有的结点。
- 如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。
代码实现
拓补排序部分代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
/**
* 拓补排序(使用bfs)
*/
public void topoLogySort() {
Queue<Integer> queue = new LinkedList();
// 入度为0的顶点入队
for (int i = 0; i < matrix.length; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
Integer cur;
while ((cur = queue.poll()) != null) {// 出队
// 输出自己
System.out.print(vertexNames.get(cur) + " ");
for (int j = 0; j < matrix[cur].length; j++) {
if (matrix[cur][j] == 1) {
// 将被当前节点指向的节点入度-1
inDegree[j]--;
// 如果入度降为0则入队
if (inDegree[j] == 0) {
queue.offer(j);
}
}
}
}
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
package com.eh.ftd.dsa.ds;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 有向无环图(拓补排序)
*
* @author David Li
* @create 2020/07/01 18:46
*/
public class DAG {
/**
* 图的邻接矩阵表现形式
*/
private int[][] matrix;
/**
* 顶点的表现形式
*/
private List<String> vertexNames;
/**
* 入度
*/
private int[] inDegree;
/**
* 构造器
*
* @param vertexNames 顶点名称数组
*/
public DAG(String[] vertexNames) {
this.matrix = new int[vertexNames.length][vertexNames.length];
this.vertexNames = Arrays.asList(vertexNames);
inDegree = new int[vertexNames.length];
}
private int getIndexByVertexName(String vertexName) {
for (int i = 0; i < vertexNames.size(); i++) {
if (vertexName.equals(vertexNames.get(i))) {
return i;
}
}
throw new RuntimeException();
}
/**
* 有方向的，v1->v2
*
* @param v1
* @param v2
*/
public void buildEdge(String v1, String v2) {
int idx1 = getIndexByVertexName(v1);
int idx2 = getIndexByVertexName(v2);
matrix[idx1][idx2] = 1;
matrix[idx2][idx1] = 0;
inDegree[idx2]++;
}
/**
* 拓补排序(使用bfs)
*/
public void topoLogySort() {
Queue<Integer> queue = new LinkedList();
// 入度为0的顶点入队
for (int i = 0; i < matrix.length; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
Integer cur;
while ((cur = queue.poll()) != null) {// 出队
// 输出自己
System.out.print(vertexNames.get(cur) + " ");
for (int j = 0; j < matrix[cur].length; j++) {
if (matrix[cur][j] == 1) {
// 将被当前节点指向的节点入度-1
inDegree[j]--;
// 如果入度降为0则入队
if (inDegree[j] == 0) {
queue.offer(j);
}
}
}
}
}
public static void main(String[] args) {
String[] vertexNames = {"1", "2", "3", "4", "5"};
DAG graph = new DAG(vertexNames);
graph.buildEdge("1", "2");
graph.buildEdge("1", "3");
graph.buildEdge("2", "3");
graph.buildEdge("2", "4");
graph.buildEdge("3", "4");
graph.buildEdge("3", "5");
graph.topoLogySort();
}
}
|
参考
深入理解拓扑排序（Topological sort)
如上图有两个拓补排序结果：[1, 2, 3, 4, 5]和[1, 2, 3, 5, 4]。