Javaを使用してトポロジカルソートアルゴリズムを実装する方法

class Graph { private int V; // 图的顶点数 private LinkedList adj[]; // 邻接表 Graph(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) { adj[i] = new LinkedList<>(); } } // 添加边 void addEdge(int v, int w) { adj[v].add(w); } }

import java.util.*; class TopologicalSort { // 拓扑排序算法 void topologicalSort(Graph graph) { int V = graph.V; LinkedList adj[] = graph.adj; int[] indegree = new int[V]; for (int i = 0; i < V; ++i) { for (int j : adj[i]) { indegree[j]++; } } Queue queue = new LinkedList<>(); for (int i = 0; i < V; ++i) { if (indegree[i] == 0) { queue.add(i); } } int count = 0; ArrayList result = new ArrayList<>(); while (!queue.isEmpty()) { int u = queue.poll(); result.add(u); for (int v : adj[u]) { if (--indegree[v] == 0) { queue.add(v); } } count++; } if (count != V) { System.out.println("图中存在环，无法进行拓扑排序"); return; } System.out.println("拓扑排序结果："); for (int i : result) { System.out.print(i + " "); } System.out.println(); } }

public class Main { 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); TopologicalSort topologicalSort = new TopologicalSort(); topologicalSort.topologicalSort(graph); } }