Topological Sort

这里讨论一下拓扑排序,以及怎么检查有向图有没有带环。

DAG介绍

DAG叫有向无环图,他描述了整个连通图中的某个子图不能带有环的,只要有环,就不能称为有向无环图。

title

下图是错误的,带环的图。

title

拓扑排序介绍

拓扑排序该算法在1972年设计编译器时被发明出来,当时的问题是,怎么解决代码编译的依赖问题。因为代码都是有顺序的,例如:C代码文件依赖B代码文件,B依赖A,B依赖D,那在编译时就不能先编译B,得将A和D先编译完了,才能编译B。所以编译的顺序要么是[A,D,B,C],要么是[D,A,B,C]。拓扑排序可以将图转为顺序表,挨个打印这个表,就是正确的顺序了。

关于拓扑排序的实现有很多办法BFS、DFS、Kahn都可以实现,下面用Kahn实现以一下。

Kahn算法实现

关于代码的实现不复杂下面简单理一下实现思路:

定义数据结构的时候,如果s需要先于t执⾏,那就添加⼀条s指向t的边。所以,如果某个顶点⼊度为0, 也就表示,没有任何顶点必须先于这个顶点执⾏,那么这个顶点就可以执⾏了。

我们先从图中,找出⼀个⼊度为0的顶点,将其输出到拓扑排序的结果序列中(对应代码中就是把它打印出来),并且把这个顶点从图中删除(也就是把这个顶点可达的顶点的⼊度都减1)。我们循环执⾏上⾯的过程,直到所有的顶点都被输出。最后输出的序列,就是满⾜局部依赖关系的拓扑排序。

下面是代码简单思路

下面Java实现拓扑排序(有向图是用邻接表的方式存储):

  • 初始化图顶点的入度
  • 将入度为0的顶点放到辅助队列T
  • 当T不为空,就取出队列的顶点,并从T中删除
  • 把取出的顶点放入队列Q中,并且把这个顶点从图中删除(也就是把这个顶点可达的顶点的⼊度都减1),如果入度为0,将其放到T,等下次循环,否则什么都不做。

关于有向无环图的邻接表实现可以看一下这个源码

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
//辅助队列T
private Queue<Integer> queue;

public int sort(ListDG listDG){
ListDG.VNode[] vNodes = listDG.getVNodes();

int index = 0;
queue = new LinkedList<Integer>();
char[] res = new char[vNodes.length];
int[] ins = new int[vNodes.length];

// 初始化所有顶点的入度
for (int i = 0; i < vNodes.length; i++) {
ListDG.ENode edges = vNodes[i].firstEdge;
while(edges != null){
ins[edges.index]++;
edges = edges.next;
}
}

//将入度为0的顶点放入到队列中
for (int i = 0; i < ins.length; i++) {
if(ins[i] == 0)
queue.add(i);
}

while(!queue.isEmpty()){
int v = queue.remove();
res[index++] = vNodes[v].data;

// 获取到所有的边
ListDG.ENode edges = vNodes[v].firstEdge;
while(edges != null){
// 这里入度-1,就当做删除边操作了
ins[edges.index]--;

if(ins[edges.index] == 0)
queue.add(edges.index);

edges = edges.next;
}
}

if(index != vNodes.length){
System.out.println("图有环");
return 1;
}

// 遍历T队列
System.out.print("图的拓扑排序结果为:");
for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + "\t");
}

return 0;
}

算法时间复杂度

从Kahn代码中可以看出来,每个顶点被访问了⼀次,每个边也都被访问了⼀次,所以,Kahn算法的时间复杂度就是O(V+E)(V表示顶点个数,E表示边的个数)。

图有没有带环

其实检查环的问题。只适用于,已知一个图,检查图中环的场景,看顺序表中的length是不是为顶点的个数就能监测是不是有环,因为它的效率真的是太低了,要处理完整个图才能看到结果。比如场景:已知数据库中的所有顶点的依赖关系了,检查顶点间到底有没有环。这个问题,就需要⽤到拓扑排序算法了。我们把关系从数据库中加载到内存,然后构建成这种有向图数据结构,再利⽤拓扑排序,拿到排序完的顺序表,检查环。

另外一种场景就是,插入一个关系以后,监测是否出现环,这时候再用拓扑排序显然性能有点low,下面介绍一个稍微好点的。举个例子比如下图:

title

这个时候插入C指向A的边以后,怎么监测带没带环?使用BFS或者DFS遍历顶点,用哈希表记录已访问过的顶点值。

1
HashSet<Integer> hashTable = new HashSet<>(); // 保存已经访问过的vertex

然后如果放的时候发现哈希表里面已经存在,那就意味着出现环了。

方便折腾的时候参考,源码