详解Java实现拓扑排序算法

什么是拓扑排序算法

拓扑排序算法是一种用来解决有向图中节点之间依赖关系问题的算法，它可以将有向无环图（DAG）中的所有节点按照一定的规则排序，可以用来确定一组任务的执行顺序，比如编译器可以用拓扑排序来确定源代码的编译顺序。

拓扑排序算法原理

拓扑排序算法基于DAG图，DAG图中每个节点表示一个任务，有向边表示任务之间的依赖关系，如果节点a到节点b有一条有向边，则表示节点a必须在节点b之前执行。拓扑排序算法就是将DAG中的节点按照依赖关系排序的过程。

拓扑排序算法的过程如下：

1. 建立入度表和邻接表：

   • 入度表：用于保存每个节点的入度，入度为0的节点没有依赖关系，可以作为排序的起点；
   • 邻接表：用于记录每个节点的出度，即它所指向的其他节点。

2. 创建一个队列，将初始入度为0的节点加入队列中。

3. 对于队列中的节点，遍历其邻接节点，并将邻接节点的入度减1，如果减为0，则将其加入队列中。

4. 不断重复步骤3，直到队列为空，或者所有节点都已被遍历。

5. 最终的结果是排序后的节点列表，如果队列为空而图中还有未遍历的节点，则表示图中存在环路。

Java实现拓扑排序算法

在Java中实现拓扑排序算法，可以通过建立入度表和邻接表，并使用BFS（广度优先搜索）算法来进行遍历和排序。

下面是Java实现拓扑排序算法的详细示例代码：

import java.util.*;

public class TopologicalSorting {

    private Map<Integer, List<Integer>> adjacencyList;
    private Map<Integer, Integer> indegree;

    public void topoSort(int n, int[][] edges) {
        adjacencyList = new HashMap<>();
        indegree = new HashMap<>();

        // 初始化邻接表和入度表
        for (int i = 0; i < n; i++) {
            adjacencyList.put(i, new ArrayList<>());
            indegree.put(i, 0);
        }

        // 建立邻接表和入度表
        for (int[] edge : edges) {
            adjacencyList.get(edge[0]).add(edge[1]);
            indegree.put(edge[1], indegree.get(edge[1]) + 1);
        }

        // 初始化队列，将入度为0的节点加入队列中
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree.get(i) == 0) {
                queue.offer(i);
            }
        }

        // 遍历队列中的节点，并更新其邻接节点的入度
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int neighbor : adjacencyList.get(node)) {
                indegree.put(neighbor, indegree.get(neighbor) - 1);
                if (indegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 判断是否存在环路
        if (result.size() != n) {
            throw new RuntimeException("The given graph contains a cycle");
        }

        // 输出排序结果
        System.out.println("Topological sorting result:");
        for (int i : result) {
            System.out.print(i + " ");
        }
    }

    public static void main(String[] args) {
        int n = 7;
        int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {3, 5}, {4, 5}, {5, 6}};
        TopologicalSorting ts = new TopologicalSorting();
        ts.topoSort(n, edges);
    }
}

上述代码中，我们通过建立邻接表和入度表，利用BFS算法进行排序，并在最后输出排序结果。

示例说明

在上面的Java代码示例中，我们使用了以下示例图来进行拓扑排序：

          5 --> 6
         /       ↑
        ↓        |
0 --> 1 --> 2 --> 4
        |      /↑
        ↓     /
        3 --<

运行上述Java程序，输出的排序结果是：0 1 2 3 4 5 6。

我们可以再使用另外一个示例图来进行说明：

0 --> 1 --> 2 --> 3
        |      /↑
        |     /
        |    ↓
        5 <-- 4

在上述示例图中，节点0没有任何依赖，是排序的起点。我们可以修改Java代码中的邻接表和入度表，并重新运行程序，即可得到0 1 4 2 3 5的排序结果。

总的来说，拓扑排序算法是对有向无环图（DAG）中的节点进行排序的一种算法，它可以被广泛地应用于各种领域，如编译器、调度器等。在Java中，我们可以通过建立邻接表和入度表，并使用BFS算法进行排序来实现拓扑排序算法。