Java如何实现拓扑排序

拓扑排序是一种用于有向无环图（DAG）的线性排序算法，它将图中的所有节点排列成一个线性序列，使得对于图中的每一条有向边 (u, v)，节点 u 在序列中都位于节点 v 的前面。拓扑排序常用于任务调度、依赖关系分析等场景。

在Java中，拓扑排序可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。本文将介绍如何使用BFS（Kahn算法）来实现拓扑排序。

1. 拓扑排序的基本概念

拓扑排序的前提是图必须是有向无环图（DAG）。如果图中存在环，则无法进行拓扑排序。拓扑排序的结果不唯一，可能存在多个合法的排序序列。

2. 使用BFS实现拓扑排序

BFS实现拓扑排序的核心思想是通过维护一个入度表（indegree table），记录每个节点的入度（即有多少条边指向该节点）。算法步骤如下：

1. 初始化一个队列，将所有入度为0的节点加入队列。
2. 从队列中取出一个节点，将其加入拓扑排序的结果中。
3. 将该节点的所有邻接节点的入度减1，如果某个邻接节点的入度变为0，则将其加入队列。
4. 重复步骤2和3，直到队列为空。
5. 如果拓扑排序结果中的节点数量与图中的节点数量相同，则说明拓扑排序成功；否则，图中存在环，无法进行拓扑排序。

3. Java代码实现

下面是一个使用BFS实现拓扑排序的Java代码示例：

import java.util.*;

public class TopologicalSort {

    public static List<Integer> topologicalSort(int numVertices, List<List<Integer>> adjacencyList) {
        // 初始化入度表
        int[] indegree = new int[numVertices];
        for (List<Integer> neighbors : adjacencyList) {
            for (int neighbor : neighbors) {
                indegree[neighbor]++;
            }
        }

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

        // 进行拓扑排序
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);

            // 将该节点的所有邻接节点的入度减1
            for (int neighbor : adjacencyList.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 如果结果中的节点数量与图中的节点数量相同，则返回结果；否则，图中存在环
        if (result.size() == numVertices) {
            return result;
        } else {
            throw new IllegalStateException("图中存在环，无法进行拓扑排序");
        }
    }

    public static void main(String[] args) {
        int numVertices = 6;
        List<List<Integer>> adjacencyList = new ArrayList<>();
        adjacencyList.add(Arrays.asList(1, 2)); // 0 -> 1, 0 -> 2
        adjacencyList.add(Arrays.asList(3, 4)); // 1 -> 3, 1 -> 4
        adjacencyList.add(Arrays.asList(4, 5)); // 2 -> 4, 2 -> 5
        adjacencyList.add(Arrays.asList());     // 3 -> 
        adjacencyList.add(Arrays.asList(5));    // 4 -> 5
        adjacencyList.add(Arrays.asList());     // 5 -> 

        List<Integer> sortedOrder = topologicalSort(numVertices, adjacencyList);
        System.out.println("拓扑排序结果: " + sortedOrder);
    }
}

4. 代码解析

• adjacencyList 是一个邻接表，表示图的结构。adjacencyList.get(i) 返回节点 i 的所有邻接节点。
• indegree 数组用于记录每个节点的入度。
• queue 是一个队列，用于存储当前入度为0的节点。
• result 列表用于存储拓扑排序的结果。

5. 运行结果

运行上述代码，输出结果为：

拓扑排序结果: [0, 1, 2, 3, 4, 5]

这个结果表示一个合法的拓扑排序序列。

6. 总结

拓扑排序是一种重要的图算法，适用于有向无环图。通过BFS实现的拓扑排序算法时间复杂度为O(V + E)，其中V是节点数量，E是边数量。在实际应用中，拓扑排序常用于解决任务调度、依赖关系分析等问题。

通过本文的介绍和代码示例，你应该能够在Java中实现拓扑排序，并理解其背后的原理。