Java 实现拓扑排序算法（源代码）
需积分: 1 142 浏览量
2024-05-16
17:26:02
上传
评论
收藏 141KB PDF 举报
拓扑排序（Topological Sorting）是对DAG（有向无环图，Directed Acyclic Graph）的顶点进行排序，使得
对每一条有向边 (u, v)，均有 u（在排序记录中）比 v 先出现。它通常用于在具有依赖关系的任务中确定任务
的执行顺序。
算法原理
拓扑排序的算法原理主要基于以下几个步骤：
1. 选择一个没有前驱（即入度为0）的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复上述两步，直到当前的DAG为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必
然存在环。
实现步骤
1. 创建一个队列，用于存放入度为0的顶点。
2. 创建一个数组或列表，用于存放拓扑排序的结果。
3. 创建一个数组或列表，用于记录每个顶点的入度。
4. 遍历所有顶点，如果某个顶点没有前驱（即入度为0），则将其加入队列。
5. 当队列不为空时，执行以下操作：
从队列中取出一个顶点，并添加到结果列表中。
遍历该顶点的所有邻接点，将它们的入度减1。
如果邻接点的入度变为0，则将其加入队列。
6. 如果结果列表中的顶点数不等于DAG中的顶点数，则说明图中存在环，无法进行拓扑排序。
Java代码实现
import java.util.*;
public class TopologicalSort {
private static class Graph {
private int V; // 顶点数量
private LinkedList<Integer> adj[]; // 邻接表
private int inDegree[]; // 入度数组
Graph(int v) {
V = v;
adj = new LinkedList[v];
inDegree = new int[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList<>();
}
void addEdge(int v, int w) {
adj[v].add(w);
inDegree[w]++; // 增加w的入度
资源评论
