用java实现拓补排序
时间: 2023-10-01 22:05:54 浏览: 83
拓扑排序是一种常见的图论算法,可以用来确定有向无环图(DAG)的顶点线性序列。以下是用 Java 实现拓扑排序的示例代码:
```java
import java.util.*;
public class TopologicalSort {
public static List<Integer> sort(int[][] graph) {
// 计算每个顶点的入度
int[] inDegree = new int[graph.length];
for (int[] edge : graph) {
inDegree[edge[1]]++;
}
// 将入度为 0 的顶点加入队列
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
// 依次取出队列中的顶点,并删除其所有出边
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int v = queue.poll();
result.add(v);
for (int[] edge : graph) {
if (edge[0] == v) {
inDegree[edge[1]]--;
if (inDegree[edge[1]] == 0) {
queue.offer(edge[1]);
}
}
}
}
// 如果图中存在环,则返回空列表
if (result.size() != graph.length) {
return Collections.emptyList();
}
return result;
}
public static void main(String[] args) {
int[][] graph = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
List<Integer> result = sort(graph);
if (result.isEmpty()) {
System.out.println("The graph contains a cycle.");
} else {
System.out.println(result);
}
}
}
```
在这个示例中,我们使用邻接表来表示图,其中 `graph[i][0]` 表示从顶点 `i` 出发的边的终点,`graph[i][1]` 表示边的终点。我们首先计算每个顶点的入度,并将入度为 0 的顶点加入队列。然后,我们依次取出队列中的顶点,并删除其所有出边。如果图中存在环,则返回空列表。否则,返回拓扑排序结果。
阅读全文