拓扑排序

拓扑排序是用于有向无环图（DAG）的一种排序方式，它可以用来表示依赖关系，任务调度等情况。下面是一个拓扑排序的Java代码示例：

import java.util.*;

public class TopologicalSort {

    public static List<Integer> topologicalSort(int vertices, List<Integer>[] graph) {
        List<Integer> result = new ArrayList<>();
        int[] inDegree = new int[vertices];

        // 计算每个顶点的入度
        for (List<Integer> neighbors : graph) {
            for (int neighbor : neighbors) {
                inDegree[neighbor]++;
            }
        }

        // 将入度为0的顶点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 逐步移除入度为0的顶点，并更新相关顶点的入度
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            result.add(vertex);

            for (int neighbor : graph[vertex]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int vertices = 6;
        List<Integer>[] graph = new ArrayList[vertices];
        for (int i = 0; i < vertices; i++) {
            graph[i] = new ArrayList<>();
        }

        graph[5].add(2);
        graph[5].add(0);
        graph[4].add(0);
        graph[4].add(1);
        graph[2].add(3);
        graph[3].add(1);

        List<Integer> result = topologicalSort(vertices, graph);
        System.out.println("Topological Sort: " + result);
    }
}

在这个示例中，topologicalSort 方法使用拓扑排序算法对给定的有向无环图（使用邻接表表示）进行排序。该算法的核心思想是从入度为0的顶点开始，逐步移除顶点并更新相关顶点的入度。