java实现拓扑排序的方法

以下是Java实现拓扑排序的方法：

1.使用邻接表来表示图，并初始化每个节点的入度为0。

2.遍历所有的边，将每个节点的入度加1。

3.将入度为0的节点加入队列中。

4.当队列不为空时，取出队首节点，将其加入拓扑排序结果中，并将其所有邻接节点的入度减1。

5.若邻接节点的入度为0，则将其加入队列中。

6.重复步骤4和5，直到队列为空。

以下是Java代码示例：

import java.util.*;

public class TopologicalSort {
    public int[] topoSort(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        List<List<Integer>> adjList = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        int[] result = new int[numCourses];
        int index = 0;

        // 初始化邻接表和入度数组
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int[] edge : prerequisites) {
            adjList.get(edge[1]).add(edge[0]);
            inDegree[edge[0]]++;
        }

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

        // 拓扑排序
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result[index++] = node;
            for (int neighbor : adjList.get(node)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 判断是否存在环
        if (index != numCourses) {
            return new int[0];
        }

        return result;
    }
}