图论16-拓扑排序

1 拓扑排序

• 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。

• 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

2 拓扑排序的普通实现

2.1 算法实现 - 度数为0入队列

Queue<Integer> q = new LinkedList<>();for(int v = 0; v < G.V(); v ++){indegrees[v] = G.indegree(v);//入度度数为0的入队，找源点if(indegrees[v] == 0) q.add(v);
}while(!q.isEmpty()){ // 如果有环，那么环上的点从入口开始就无法进入队列int cur = q.remove();//相邻的顶点入队res.add(cur);//相邻的顶点入度都减1for(int next: G.adj(cur)){indegrees[next] --;// 入度为0的直接入队if(indegrees[next] == 0) q.add(next);}
}

2.2 拓扑排序中的环检测

能够进行拓扑排序的图是没有环的，否则无法进行拓扑排序。
在拓扑排序的实现过程中，如果返回的res数组中的点的数量与图的点的数量不一致，则说明有环。因为环上的点由于度数无法为0，无法进入队列，从而进入res数组返回答案。

if(res.size() != G.V()){hasCycle = true;res.clear();
}

3 深度优先遍历的后续遍历

• 根节点最后遍历，讲得到的序列反过来，就是拓扑排序，但是这种方法无法实现环检测。
  

3.1 使用环检测类先判断是否有环

private boolean hasCycle = false;hasCycle = (new DirectedCycleDetection(G)).hasCycle();if(hasCycle) return;

3.2 调用无向图的深度优先后续遍历方法，进行DFS

GraphDFS dfs = new GraphDFS(G);for(int v: dfs.post())res.add(v);