拓扑排序

摘自https://blog.csdn.net/qq_37618797/article/details/81070577

定义：


把AOV网（用定点表示活动，用弧表示活动间优先关系的有向图）络中各个顶点按照它们互相之间的优先关系排列成一个线性序列的过程叫做拓扑排序。

方法：


在有向图中选一个没有前驱的顶点并且输出
从图中删除该顶点和所有以它为尾的弧，即删除所有与它有关的边。
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

例题：

首先我们找到无前驱顶点C1和C9，我们删除掉C1，输出C1，并删除所有与C1相连的边

接着再从C2，C4，C9这三个无前驱顶点中选择一个删除掉，我们删除C2，输出C2，并删除所有与C2相连的边

最终得拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8。

注意：拓扑序列并不唯一，C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8 也是一种拓扑序列。

关键代码

public void topoSort() throws Exception{
        int count = 0;//判断是否所有的顶点都出队了,若有顶点未入队(组成环的顶点)，则这些顶点肯定不会出队
        
        Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.
        //扫描所有的顶点,将入度为0的顶点入队列
        Collection<Vertex> vertexs = directedGraph.values();
        for (Vertex vertex : vertexs)
            if(vertex.inDegree == 0)
                queue.offer(vertex);
        //度为0的顶点出队列并且更新它的邻接点的入度
        while(!queue.isEmpty()){
            Vertex v = queue.poll();
            System.out.print(v.vertexLabel + " ");//输出拓扑排序的顺序
            count++;
            for (Edge e : v.adjEdges) 
                if(--e.endVertex.inDegree == 0)
                    queue.offer(e.endVertex);
        }
        if(count != directedGraph.size())
            throw new Exception("Graph has circle");
    }

输出：

拓扑序列：1 2 3 4 5 7 9 10 11 12 6 8

实例

如果含有圈，不可能进行拓扑排序，在这里我们假设图中不含圈。要将下图进行拓扑：

我们计算每个顶点的入度，将所有入读为零的顶点放入初始为空的队列，当队列不为空，删除一个顶点v，并将与v邻接的所有顶点的入度均减1。只要一个顶点的入度降为0，就把该点放入队列中。排序就是顶点出队的顺序。
 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Test {
    //有向图的邻接矩阵表示法
    static int [] [] matrix = {
            {1,1,1,1,0,0,0},
            {0,1,0,1,1,0,0},
            {0,0,1,0,0,1,0},
            {0,0,1,1,0,1,1},
            {0,0,0,1,1,0,1},
            {0,0,0,0,0,1,0},
            {0,0,0,0,0,1,1} };

    static int [] indegree = new int [7];
    static int [] num = new int [7];

    static void topsort() {
        Queue<Integer> q = new LinkedList<>();
        int counter = 0;

        for(int i = 0; i < 7; i++) 
            if (indegree[i] == 0)
                q.offer(i);

        while( !q.isEmpty() ) {
            int v = q.poll();
            num[v] = counter++;

            for(int i = 0; i < 7; i++) 
                if(v != i && matrix[v][i] == 1 && --indegree[i] == 0) 
                    q.offer(i);
        }
    }

    public static void main(String [] args) {
        for(int i = 0; i < 7; i++) {
            for(int j = 0; j < 7; j++)
                if(matrix[j][i] == 1)
                    indegree[i]++;
            indegree[i]--;
        }

        topsort();
        System.out.println("各点拓扑编号：" + Arrays.toString(num));
    }

}