Java语言实现拓扑排序（Topological Sorting）算法

拓扑排序是一种线性排序方法，通常用于有向无环图（DAG, Directed Acyclic Graph）。它将图中的顶点排序，使得对于每一条有向边 u -> v，顶点 u 在 v 之前。常见的实现方法有Kahn算法和深度优先搜索（DFS）。

以下是使用Kahn算法和DFS的Java实现：

使用Kahn算法的实现

Kahn算法是一种基于入度的算法。它的步骤如下：

1. 计算所有顶点的入度。
2. 将所有入度为0的顶点加入队列。
3. 当队列不为空时，取出队首元素，将其加入拓扑排序结果中，并将其所有邻接点的入度减1。如果某个邻接点的入度变为0，则将其加入队列。
4. 如果处理的顶点数等于图中的顶点数，则存在拓扑排序，否则图中存在环

import java.util.*;

public class TopologicalSortKahn {
    public static List<Integer> topologicalSort(int numVertices, List<List<Integer>> edges) {
        List<Integer> result = new ArrayList<>();
        int[] inDegree = new int[numVertices];
        Map<Integer, List<Integer>> graph = new HashMap<>();
        
        // 初始化图和入度
        for (int i = 0; i < numVertices; i++) {
            graph.put(i, new ArrayList<>());
        }
        
        for (List<Integer> edge : edges) {
            int from = edge.get(0);
            int to = edge.get(1);
            graph.get(from).add(to);
            inDegree[to]++;
        }
        
        // 将所有入度为0的顶点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numVertices; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        
        // 处理队列中的顶点
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            
            for (int neighbor : graph.get(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
        
        if (result.size() != numVertices) {
            throw new RuntimeException("The graph has a cycle!");
        }
        
        return result;
    }

    public static void main(String[] args) {
        int numVertices = 6;
        List<List<Integer>> edges = Arrays.asList(
            Arrays.asList(5, 2),
            Arrays.asList(5, 0),
            Arrays.asList(4, 0),
            Arrays.asList(4, 1),
            Arrays.asList(2, 3),
            Arrays.asList(3, 1)
        );
        
        System.out.println("Topological Sort (Kahn's Algorithm): " + topologicalSort(numVertices, edges));
    }
}