引言
工程中尝尝氛围很多步骤完成，有些步骤可以同步进行，而有些步骤需要某些步骤完成后才能进行，如何安排它们的流程是项目实施要考虑的重要问题，这就是拓扑排序问题。拓扑排序，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
拓扑排序思想
1.在有向图中选一个没有前驱的顶点并且输出;
2.从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）;
3.重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。
拓扑排序有点像抽丝剥茧，每一次遍历都会去掉最外层的"壳"，抽完为止。
图解
1.针对下图:
有入度0的顶点V1和V6,先把他们放入集合S=[V1,V6]，这里随机取出V6遍历,S=[V1]。
2.V6遍历完，去掉和V4、V5的边(入度减1)，图结构如下:
3.从集合中取出V1,删除边，V2、V3、V4入度减一后,V4和V3入度为0，S=[V3,V4],图结构如下:
4.从集合中取出V4或者V3(取哪一个看具体算法),这里取V4,V5入度为减一不为0,S为[V3],图结构为:
5,从集合中取出V3，V2、V5入度为0，S=[V2,V5]，图结构如下:
image
6.继续输出集合中蒸鱼顶点，最后的该图的一个拓扑排序结果为:
v6—>v1—>v4—>v3—>v5—>v2。
注意:拓扑排序仅反应顶点间的层序关系，输出结果不唯一。
代码实现
代码实现，我们引入一个集合(栈或者队列均可)，存放未遍历的入度为0的顶点;引入计数变量检测图是否遍历完。具体实现如下:
package graphic;
import queue.Queue;
/**
* Created by chenming on 2018/6/16
* 拓扑排序
*/
public class TopologySort {
private class VNode {
int value;//值
int inDegree;//入度
}
private int[][] map;//邻接矩阵
private VNode[] nodes;
public TopologySort(int[][] map) {
this.map = map;
nodes = new VNode[map.length];
for (int i = 0; i < map.length; i++) {
//初始化入度
VNode node = new VNode();
node.value = i;
node.inDegree = getIndegree(i);
nodes[i] = node;
}
}
/**
* 从邻接矩阵中得到顶点入度
*
* @param index
* @return
*/
private int getIndegree(int index) {
int in = 0;
for (int i = 0; i < map.length; i++) {
if (0 < map[i][index] && map[i][index] < Integer.MAX_VALUE) {
in++;
}
}
return in;
}
/**
* 有向图的拓扑排序,，思路如下:
* 1,类似广度优先遍历,引入队列保存入度为0的未遍历节点
* 2.每去掉一个顶点，则去掉该顶点的边，即它所有邻接顶点的顶点入度-1，如果为0则加入队列
* 3.循环执行步骤2，直到队列为空
* 4.循环结束检测是否遍历完整，如果没有遍历完全，则表示有回环
*/
public void topologySort() {
Queue<Integer> queue = new Queue<>();//保存入度为0的索引
int numb = map.length;
int count = 0;//校验用
//收集入度为0的顶点
for (int i = 0; i < numb; i++) {
if (nodes[i].inDegree == 0) {
queue.enquene(i);
}
}
while (!queue.isEmpty()) {
int index = queue.dequeue();
System.out.println("拓扑排序:" + index);
count++;
//遍历完"删除"顶点index的所有边,即减少它邻接顶点的入度
for (int i = 0; i < numb; i++){
if(map[index][i] > 0 && map[index][i] < Integer.MAX_VALUE){
if(--nodes[i].inDegree == 0){
//入度减一后，加入队列
queue.enquene(i);
}
}
}
}
if(count != numb){
throw new RuntimeException("图中存在回环");
}
}
}
测试图用例:
拓扑排序用例.png
测试代码:
@Test
public void testTopol() {
int INF = Integer.MAX_VALUE;
int[][] map = {
{0, INF, INF, INF, 1, 1, INF, INF, INF, INF, INF, 1, INF, INF},//0
{INF, 0, 1, INF, 1, INF, INF, INF, 1, INF, INF, INF, INF, INF},//1
{INF, INF, 0, INF, INF, 1, 1, INF, INF, 1, INF, INF, INF, INF},//2
{INF, INF, 1, 0, INF, INF, INF, INF, INF, INF, INF, INF, INF, 1},//3
{INF, INF, INF, INF, 0, INF, INF, 1, INF, INF, INF, INF, INF, INF},//4
{INF, INF, INF, INF, INF, 0, INF, INF, 1, INF, INF, INF, 1, INF},//5
{INF, INF, INF, INF, INF, 1, 0, INF, INF, INF, INF, INF, INF, INF},//6
{INF, INF, INF, INF, INF, INF, INF, 0, INF, INF, INF, INF, INF, INF},//7
{INF, INF, INF, INF, INF, INF, INF, 1, 0, INF, INF, INF, INF, INF},//8
{INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, 1, 1, INF, INF},//9
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, INF, 1},//10
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, INF},//11
{INF, INF, INF, INF, INF, INF, INF, INF, INF, 1, INF, INF, 0, INF},//12
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0},//13
};
TopologySort ts = new TopologySort(map);
ts.topologySort();
}
输出:
拓扑排序:0
拓扑排序:1
拓扑排序:3
拓扑排序:4
拓扑排序:2
拓扑排序:6
拓扑排序:5
拓扑排序:8
拓扑排序:12
拓扑排序:7
拓扑排序:9
拓扑排序:10
拓扑排序:11
拓扑排序:13
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
网友评论