Java实现拓扑排序的示例代码

下面是Java实现拓扑排序的完整攻略：

1. 理解拓扑排序的概念

拓扑排序是一种常用于有向无环图（DAG）的算法，用于确定图中所有节点的相对顺序关系。具体来说，拓扑排序可以将一个DAG的所有节点线性排序，使得对于任何一条有向边(u, v)，起点u在拓扑排序中都出现在终点v的前面。

2. 实现拓扑排序的算法

一个直接的想法是通过深度优先搜索（DFS）来实现拓扑排序。首先，我们需要先构建DAG模型，然后从任意一个节点开始进行DFS搜索，具体如下：

1. 对于起始节点start，递归访问它的所有出边，对于每一条出边(u, v)，递归访问v节点的所有出边；
2. 当某个节点v没有未访问的出边时，将v节点添加到顺序列表中，表示v节点可以在排序中出现在它的所有前驱节点之后；
3. 重复以上过程，直到所有的节点都被添加到顺序列表中，所得到的顺序列表即为一种拓扑排序的序列。

3. 示例说明

示例1

假设有下面这个图，我们可以通过拓扑排序来确定节点间的执行顺序关系：

    1 -> 3 -> 5
    |         ^
    v         |
    2 -------> 4

我们从任意一个节点开始进行DFS搜索，比如从节点1开始，具体步骤如下：

1. 访问节点1，递归访问节点3；
2. 访问节点3，递归访问节点5；
3. 将节点5加入到顺序列表中；
4. 回溯到节点3，访问节点4；
5. 将节点4加入到顺序列表中；
6. 回溯到节点1，访问节点2；
7. 将节点2加入到顺序列表中。

至此，所有节点都已被添加到顺序列表中，所得到的拓扑排序序列是[1, 3, 2, 5, 4]。

示例2

假设现在有一个更复杂的图，其中包含一个环路：

    1 -> 2 -> 3
          ^    |
          |    v
          5 <- 4

这时候我们使用上述DFS搜索的方法不再适用，因为存在环路导致无法确定节点的相对顺序。但是，可以使用另外一种更加高效的拓扑排序算法——Kahn算法。

• Kahn算法：

先建一个入度表inDegree，记录每个节点的入度，即有多少条边指向该节点。节点的入度为0表示该节点是入口节点。具体步骤如下：

1. 从所有入口节点开始将其入队，入队的顺序不影响最后的输出结果；
2. 当队列不空时，取出队首节点，将其邻接节点的入度减一，若邻接节点入度变为0，则将其入队；
3. 重复步骤2直到队列为空，最后输出的序列即为一种可行的拓扑排序序列。

对于上面这个图，Kahn算法可以生成的任意一种可行拓扑排序序列是[1, 2, 3, 5, 4]。

代码实现：

下面给出Java实现拓扑排序的示例代码，包括使用DFS搜索和Kahn算法两种方式实现：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;

class Graph {
    private int V; // 图中顶点个数
    private List<Integer>[] adjList; // 记录图中边的信息

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

    // 添加有向边
    public void addEdge(int u, int v) {
        adjList[u].add(v);
    }

    // 拓扑排序（DFS） 
    public List<Integer> topoSortDFS() {
        List<Integer> order = new ArrayList<>();
        boolean[] visited = new boolean[V];

        // 从每个未访问的节点开始进行DFS搜索
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, visited, order);
            }
        }

        return order;
    }

    // DFS搜索
    private void dfs(int u, boolean[] visited, List<Integer> order) {
        visited[u] = true;

        for (int v : adjList[u]) {
            if (!visited[v]) {
                dfs(v, visited, order);
            }
        }

        order.add(0, u); // 将节点u插入到顺序列表的最前面
    }

    // 拓扑排序（Kahn算法）
    public List<Integer> topoSortKahn() {
        List<Integer> order = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        int[] inDegree = new int[V];

        // 初始化入度表
        for (int u = 0; u < V; u++) {
            for (int v : adjList[u]) {
                inDegree[v]++;
            }
        }

        // 将所有入度为0的节点入队
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 循环遍历入队的节点
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);

            // 将邻接节点的入度减1，并将入度为0的加入队列中
            for (int v : adjList[u]) {
                if (--inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return order;
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(6);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);

        System.out.println(graph.topoSortDFS()); // [0, 2, 4, 1, 3, 5]
        System.out.println(graph.topoSortKahn()); // [0, 2, 1, 4, 3, 5]
    }
}

注意：本示例代码仅提供参考，可能还存在人为错误和不足之处，具体问题应结合具体实现情况进行考虑。