拓扑排序java实现

### Java 实现拓扑排序

#### AOV-网与拓扑排序的概念
在有向无环图(DAG)中，AOV网络表示活动之间的先后关系。对于给定的DAG，拓扑排序是一种线性排列这些顶点的方法，使得如果存在一条从顶点u到v的路径，则在这个序列里u会出现在v之前[^1]。

#### 使用邻接表和入度数组进行广度优先搜索(BFS)
为了有效执行拓扑排序并获得节点顺序的结果，在Java程序设计中通常采用如下策略：创建一个邻接列表用于存储图结构；初始化一个记录各结点入度数目的整型数组；利用队列辅助完成BFS遍历过程，每次从未访问过的零入度节点开始处理直至所有符合条件者被移除完毕为止[^2]。

#### 完整的Java代码实例
下面给出了一段完整的`Main.java`文件内容，展示了怎样定义Graph类以及TopologicalSort工具类来进行具体的计算工作：

import java.util.*;

public class Graph {
    private final int vertices;
    private final LinkedList<Integer>[] adjListArray;

    @SuppressWarnings("unchecked")
    public Graph(int v) {
        this.vertices = v;
        adjListArray = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjListArray[i] = new LinkedList<>();
    }

    public void addEdge(int source, int destination) {
        adjListArray[source].add(destination);
    }
}

class TopologicalSort {

    Stack<Integer> stack = new Stack<>();

    boolean[] visited;

    Integer[] indegree;

    public TopologicalSort(Graph g) {
        visited = new boolean[g.vertices];
        Arrays.fill(visited, false);

        indegree = new Integer[g.vertices];

        for (int i = 0; i < g.vertices; i++) {
            indegree[i] = 0;
        }

        for (int u = 0; u < g.vertices; u++) {
            Iterator<Integer> it = g.adjListArray[u].iterator();
            while (it.hasNext()) {
                int n = it.next();
                indegree[n]++;
            }
        }
    }

    public void topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();
        
        // 将所有入度为0的顶点加入队列
        for (int i = 0; i < indegree.length; i++)
            if (indegree[i] == 0)
                queue.add(i);

        List<Integer> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            int currentVertex = queue.poll();

            result.add(currentVertex);

            Iterator<Integer> iterator = graph.adjListArray[currentVertex].listIterator();
            while (iterator.hasNext()) {
                int nextVertex = iterator.next();
                
                indegree[nextVertex]--;
                if (indegree[nextVertex] == 0)
                    queue.add(nextVertex);
            }
        }

        if (result.size() != graph.vertices)
            System.out.println("There exists a cycle.");
        else
            System.out.println(result.toString());
    }
}

这段代码首先建立了基本的数据结构——图（由边构成），接着实现了基于Kahn算法思想的topological sort方法来判断是否存在循环依赖，并打印出可能存在的合法序列表达形式[^3]。