图的拓扑排序（Topological Sorting）是一种线性排序，用于有向无环图（Directed Acyclic Graph，DAG）。拓扑排序将图中的顶点排成一个线性序列，使得对于每一条有向边 (u, v)，顶点 u 都排在顶点 v 之前。常见的拓扑排序算法有 Kahn 算法和基于深度优先搜索（DFS）的算法。

1. Kahn 算法

Kahn 算法是一种基于入度的贪心算法，逐步选择入度为 0 的顶点并移除其出边。

步骤：

1. 计算每个顶点的入度。
2. 初始化一个队列，将所有入度为 0 的顶点入队。
3. 重复以下步骤，直到队列为空：
   • 从队列中取出一个顶点，将其添加到拓扑排序结果中。
   • 对该顶点的每条出边，将目标顶点的入度减 1。如果目标顶点的入度变为 0，则将其入队。
4. 如果结果中的顶点数与图中的顶点数相等，则拓扑排序成功，否则图中存在环。

Java实现：

import java.util.*;

public class KahnTopologicalSort {
    static class Graph {
        int V;
        List<Integer>[] adjacencyList;

        Graph(int V) {
            this.V = V;
            adjacencyList = new LinkedList[V];
            for (int i = 0; i < V; i++) {
                adjacencyList[i] = new LinkedList<>();
            }
        }

        void addEdge(int src, int dest) {
            adjacencyList[src].add(dest);
        }

        List<Integer> topologicalSort() {
            int[] inDegree = new int[V];
            for (int i = 0; i < V; i++) {
                for (int neighbor : adjacencyList[i]) {
                    inDegree[neighbor]++;
                }
            }

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

            List<Integer> topoOrder = new ArrayList<>();
            while (!queue.isEmpty()) {
                int u = queue.poll();
                topoOrder.add(u);

                for (int neighbor : adjacencyList[u]) {
                    inDegree[neighbor]--;
                    if (inDegree[neighbor] == 0) {
                        queue.add(neighbor);
                    }
                }
            }

            if (topoOrder.size() != V) {
                throw new RuntimeException("The graph has at least one cycle");
            }

            return topoOrder;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

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

2. 基于深度优先搜索的拓扑排序

DFS 算法通过递归访问顶点，确保每个顶点在所有邻居顶点之后加入结果列表。

步骤：

1. 初始化一个布尔数组，标记每个顶点是否被访问。
2. 初始化一个栈，用于存储拓扑排序结果。
3. 对每个顶点执行以下步骤（如果尚未被访问）：
   • 从该顶点开始进行 DFS。
   • 在 DFS 过程中，将当前顶点标记为已访问，并递归访问所有未被访问的邻居顶点。
   • DFS 完成后，将当前顶点压入栈。
4. 从栈顶依次弹出顶点，形成拓扑排序结果。

Java实现：

import java.util.*;

public class DFSTopologicalSort {
    static class Graph {
        int V;
        List<Integer>[] adjacencyList;

        Graph(int V) {
            this.V = V;
            adjacencyList = new LinkedList[V];
            for (int i = 0; i < V; i++) {
                adjacencyList[i] = new LinkedList<>();
            }
        }

        void addEdge(int src, int dest) {
            adjacencyList[src].add(dest);
        }

        void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {
            visited[v] = true;

            for (int neighbor : adjacencyList[v]) {
                if (!visited[neighbor]) {
                    topologicalSortUtil(neighbor, visited, stack);
                }
            }

            stack.push(v);
        }

        List<Integer> topologicalSort() {
            Stack<Integer> stack = new Stack<>();
            boolean[] visited = new boolean[V];

            for (int i = 0; i < V; i++) {
                if (!visited[i]) {
                    topologicalSortUtil(i, visited, stack);
                }
            }

            List<Integer> topoOrder = new ArrayList<>();
            while (!stack.isEmpty()) {
                topoOrder.add(stack.pop());
            }

            return topoOrder;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

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

结论

• Kahn算法：通过计算入度并逐步移除入度为 0 的顶点来实现拓扑排序。适用于在线性时间内完成排序，但需要额外的空间来存储入度。
• DFS算法：通过递归访问顶点来实现拓扑排序。适用于递归解决问题的场景，但需要维护递归栈和结果栈。