java实现图的拓扑序列（附完整源码）

以下是Java实现图的拓扑序列的完整源代码：

import java.util.*;

public class TopologicalSort {
    private int V; // 顶点数量
    private LinkedList<Integer>[] adj; // 邻接表

    public TopologicalSort(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    // 添加一条有向边
    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 拓扑排序
    public void topologicalSort() {
        // 统计每个顶点的入度
        int[] indegree = new int[V];
        for (int i = 0; i < V; ++i) {
            ListIterator<Integer> it = adj[i].listIterator();
            while (it.hasNext()) {
                int j = it.next();
                ++indegree[j];
            }
        }

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

        // 依次取出队首顶点并输出
        int count = 0;
        while (!queue.isEmpty()) {
            int i = queue.poll();
            System.out.print(i + " ");
            ++count;

            // 将所有i指向的顶点的入度减1，如果减为0则加入队列
            ListIterator<Integer> it = adj[i].listIterator();
            while (it.hasNext()) {
                int j = it.next();
                --indegree[j];
                if (indegree[j] == 0) {
                    queue.add(j);
                }
            }
        }

        // 如果count不等于V则说明图中存在环
        if (count != V) {
            System.out.println("Graph contains cycle");
        }
    }

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

        System.out.println("Topological sort:");
        g.topologicalSort();
    }
}

这里使用了邻接表来存储图，通过统计每个顶点的入度以及将入度为0的顶点加入队列的方式来实现拓扑排序。如果在排序过程中发现图中存在环，则输出 "Graph contains cycle"。在main函数中创建了一个有向图并进行了拓扑排序。