Java数据结构之有向图的拓扑排序详解

下面我将为您详细讲解“Java数据结构之有向图的拓扑排序详解”的完整攻略。

拓扑排序概述

拓扑排序是一种常见的有向无环图（DAG）的排序方法，该算法将DAG图中所有节点排序成一个线性序列，并且使得所有的依赖关系都满足从前向后的顺序关系。一般来说，DAG图的所有节点可以表示为一个任务依赖关系，而拓扑排序则可以对这些任务进行排序，确保每个任务在它所依赖的任务之后执行。

拓扑排序实现

拓扑排序可以通过以下步骤实现：

步骤一：统计每个节点的入度数

入度（in-degree）是指指向一个节点的边的数量。在拓扑排序中，统计每个节点的入度数是非常重要的，因为只有当节点的入度为0时，该节点才可以被访问。我们可以创建一个数组来表示每个节点的入度数。

int[] inDegree = new int[numCourses];
for (int[] pre : prerequisites) {
    inDegree[pre[0]]++;
}

步骤二：将所有入度为0的节点添加到队列中

我们只能开始访问入度为0的节点，因此必须将所有入度为0的节点添加到队列中。

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
    if (inDegree[i] == 0) {
        queue.offer(i);
    }
}

步骤三：遍历队列

在队列中，我们只处理入度为0的节点，并将其子节点的入度-1。如果子节点的入度变为0，则将其添加到队列中。

while (!queue.isEmpty()) {
    int cur = queue.poll();
    res[index++] = cur;
    for (int[] pre : prerequisites) {
        if (pre[1] == cur) {
            inDegree[pre[0]]--;
            if (inDegree[pre[0]] == 0) {
                queue.offer(pre[0]); // 入度为0，添加到队列中
            }
        }
    }
}

示例一

让我们通过一个简单的示例来了解拓扑排序。

给定以下依赖关系：

0 -> 1
1 -> 2
2 -> 3
3 -> 4

即4依赖于3，3依赖于2，2依赖于1，1依赖于0。

为了进行拓扑排序，我们需要统计每个节点的入度数，并将所有入度为0的节点添加到队列中。

节点	入度数
0	0
1	1
2	1
3	1
4	1

我们从入度为0的节点0开始遍历，将其子节点1的入度数-1，此时子节点1的入度数为0，将其添加到队列中。同样的，我们将子节点2的入度数-1，子节点3的入度数-1，子节点4的入度数-1，都变为0，依次添加到队列中。

经过一番遍历，最终队列中的节点顺序为0 1 2 3 4，即我们成功地将DAG图进行了拓扑排序。

示例二

假设，我们有以下依赖关系：

3 -> 2
2 -> 1
4 -> 1
4 -> 3
5 -> 4

为了进行拓扑排序，我们需要统计每个节点的入度数，并将所有入度为0的节点添加到队列中。

节点	入度数
1	2
2	1
3	1
4	0
5	0

注意到节点1的入度数为2，因此我们必须先遍历它的父节点3和4。我们从入度为0的节点4开始遍历，在遍历过程中，将子节点1的入度数-1，此时子节点1的入度数变为1，不符合入度为0的要求，因此继续遍历子节点3和5，最终将节点1的入度数变为0，添加到队列中。

接着，我们遍历节点2和节点3，最终将节点1，2，3，4，5依次添加到队列中，即我们成功地将DAG图进行了拓扑排序。

总结

拓扑排序是一种常见的有向无环图（DAG）的排序方法，它有助于解决许多依赖关系相关的问题。本文中，我们介绍了拓扑排序的实现步骤，并结合了几个示例来帮助您更好地理解它的执行过程。