拓扑排序

示例练习>>>

拓扑排序就是在一个有向无环图中，对图的顶点进行排序，排序的条件是对于任意一条有向边 <v1,v2> ，排序的结果中顶点 v1 一定在顶点 v2 的前面。如下图所示，对于 <起床，刷牙> 这条边，排序的结果中起床一定在刷牙之前。

拓扑排序的思路就是首先从图中选择入度为 0 的顶点把它加入到队列中，然后逐步输出队列中的元素 v ， 其中 v 指向的顶点入度要减 1 ，如果减 1 之后入度为 0 也要加入到队列中。重复这个步骤直到没有入度为 0 的顶点为止。其实也很好理解，入度为 0 ，说明在他前面没有顶点了，我们直接输出就行，如果入度不为 0 ，说明在他前面还有顶点，需要先输出他前面的顶点才能输出他，如图下图所示。

来看下代码：

/**
 * @param edges 邻接表
 * @param size  图的顶点个数
 */
static void topSort(List<Integer>[] edges, int size) {
    int[] inDegree = new int[size];// 记录每个顶点的入度。
    // 统计所有顶点的入度。
    for (List<Integer> edgeList : edges)
        for (int v : edgeList)
            inDegree[v]++;
    Queue<Integer> queue = new LinkedList();// 队列。
    // 将入度为0顶点入队。
    for (int i = 0; i < size; i++)
        if (inDegree[i] == 0)
            queue.offer(i);
    while (!queue.isEmpty()) {
        int v = queue.poll();// 入度为0的顶点出队。
        System.out.print(v + ",");// 打印入度为0的顶点。
        // v指向的顶点入度都要减1，如果为0需要加入到队列中。
        for (int u : edges[v])
            if (--inDegree[u] == 0)
                queue.offer(u);
    }
}

相关链接