当前位置: 首页 > news >正文

图算法之拓扑排序(Topological Sort)详细解读

拓扑排序(Topological Sort)是针对有向无环图(DAG,Directed Acyclic Graph)的一种线性排序方式,它将图中的所有顶点按顺序排列,使得对于每条有向边 (u, v),顶点 u 必须排在顶点 v 之前。拓扑排序广泛应用于任务调度、编译器语法分析、依赖管理等场景中。

拓扑排序的定义与特性

  • 有向无环图(DAG):拓扑排序仅适用于有向无环图。DAG 是一种特殊的有向图,其中不存在从某个顶点沿边可以返回该顶点的环,即不存在循环依赖。
  • 线性排序:拓扑排序为图中的顶点提供了一种线性排列方式,使得每个有向边的起点都排在终点的前面。

拓扑排序的应用

  • 任务调度问题:如果某些任务必须在其他任务之前完成,拓扑排序可以用于确定任务的执行顺序。
  • 编译器中的依赖管理:编译时,某些模块必须先于其他模块编译,拓扑排序可以确定模块的编译顺序。
  • 课程安排问题:在有前置课程要求的学习计划中,拓扑排序能够找到一个合法的课程安排顺序。

拓扑排序的两种实现方法

  1. Kahn's 算法(基于入度的广度优先搜索 BFS)
  2. 基于深度优先搜索(DFS)

1. Kahn's 算法(基于入度的 BFS)

Kahn's 算法是一种基于节点入度的算法,通过逐步移除入度为 0 的节点来生成拓扑排序。入度为 0 的节点意味着没有其他节点依赖它,因此可以将其放入排序序列中。

算法步骤
  1. 计算每个顶点的入度

    • 入度是指指向该顶点的边的数量。对于每个顶点,计算它的入度。
  2. 初始化入度为 0 的顶点队列

    • 将所有入度为 0 的顶点加入一个队列。
  3. 广度优先遍历

    • 从队列中取出一个入度为 0 的顶点,将其添加到拓扑排序的结果中。
    • 对于该顶点的每个邻居,将它们的入度减 1。如果某个邻居的入度减为 0,将其加入队列。
    • 重复此过程直到队列为空。
  4. 检查是否存在环

    • 如果最终排序中的顶点数量少于图中的顶点数量,说明图中存在环,无法进行拓扑排序。
Kahn's 算法的伪代码
function KahnTopologicalSort(Graph):in_degree = [0] * V  // 初始化所有顶点的入度为 0// 计算每个顶点的入度for each edge (u, v) in Graph:in_degree[v] += 1// 将所有入度为 0 的顶点加入队列queue = []for i = 0 to V-1:if in_degree[i] == 0:queue.append(i)topological_order = []// 广度优先遍历while queue is not empty:u = queue.pop(0)topological_order.append(u)// 对 u 的所有邻居进行处理for each neighbor v of u:in_degree[v] -= 1if in_degree[v] == 0:queue.append(v)// 检查是否存在环if len(topological_order) != V:return "Graph has a cycle"return topological_order

2. 基于深度优先搜索(DFS)的拓扑排序

DFS 方法通过递归访问每个顶点及其邻居,并在完成对邻居的递归访问后,将顶点加入到排序结果中。因此,深度优先搜索方法的拓扑排序是“后序遍历”的一种变形。

算法步骤
  1. 标记节点

    • 使用一个布尔数组 visited[] 来记录每个节点是否已经被访问。
  2. DFS 遍历

    • 对每个未被访问的节点调用 DFS,递归访问其邻居。当某个顶点的所有邻居都被处理完时,将该顶点放入结果栈中。
  3. 栈中的节点顺序

    • 由于在处理完一个节点的所有邻居后才将其放入栈,因此栈中的顺序即为拓扑排序的顺序。
DFS 拓扑排序的伪代码
function DFSTopologicalSort(Graph):visited = [False] * V  // 初始化所有顶点为未访问stack = []for each vertex v in Graph:if visited[v] == False:DFS(Graph, v, visited, stack)// 返回栈中节点的顺序即为拓扑排序的结果return stack[::-1]  // 将栈逆序输出function DFS(Graph, v, visited, stack):visited[v] = True  // 标记当前节点已访问// 递归访问所有邻居for each neighbor u of v:if visited[u] == False:DFS(Graph, u, visited, stack)// 当前节点处理完,放入栈中stack.append(v)

Java 实现

Kahn's 算法的 Java 实现
import java.util.*;public class TopologicalSortKahn {// Kahn 算法实现拓扑排序public static List<Integer> topologicalSort(int V, List<List<Integer>> adj) {int[] inDegree = new int[V];List<Integer> topOrder = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();// 计算每个节点的入度for (int i = 0; i < V; i++) {for (int neighbor : adj.get(i)) {inDegree[neighbor]++;}}// 将所有入度为 0 的节点加入队列for (int i = 0; i < V; i++) {if (inDegree[i] == 0) {queue.add(i);}}// 执行拓扑排序while (!queue.isEmpty()) {int node = queue.poll();topOrder.add(node);// 对邻居的入度进行减 1 操作for (int neighbor : adj.get(node)) {inDegree[neighbor]--;if (inDegree[neighbor] == 0) {queue.add(neighbor);}}}// 检查是否存在环if (topOrder.size() != V) {System.out.println("Graph contains a cycle");return new ArrayList<>();}return topOrder;}public static void main(String[] args) {int V = 6;List<List<Integer>> adj = new ArrayList<>(V);// 初始化邻接表for (int i = 0; i < V; i++) {adj.add(new ArrayList<>());}// 添加有向边adj.get(5).add(2);adj.get(5).add(0);adj.get(4).add(0);adj.get(4).add(1);adj.get(2).add(3);adj.get(3).add(1);// 执行拓扑排序List<Integer> result = topologicalSort(V, adj);// 输出结果if (!result.isEmpty()) {System.out.println("拓扑排序结果: " + result);}}
}
DFS 方法的 Java 实现
import java.util.*;public class TopologicalSortDFS {// DFS 实现拓扑排序public static List<Integer> topologicalSort(int V, List<List<Integer>> adj) {boolean[] visited = new boolean[V];Stack<Integer> stack = new Stack<>();// 对每个节点执行 DFSfor (int i = 0; i < V; i++) {if (!visited[i]) {dfs(i, visited, stack, adj);}}// 输出栈中的内容即为拓扑排序结果List<Integer> topOrder = new ArrayList<>();while (!stack.isEmpty()) {topOrder.add(stack.pop());}return topOrder;}private static void dfs(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> adj) {visited[node] = true;// 访问所有邻居for (int neighbor : adj.get(node)) {if (!visited[neighbor]) {dfs(neighbor, visited, stack, adj);}}// 将当前节点加入栈中stack.push(node);}public static void main(String[] args) {int V = 6;List<List<Integer>> adj = new ArrayList<>(V);// 初始化邻接表for (int i = 0; i < V; i++) {adj.add(new ArrayList<>());}// 添加有向边adj.get(5).add(2);adj.get(5).add(0);adj.get(4).add(0);adj.get(4).add(1);adj.get(2).add(3);adj.get(3).add(1);// 执行拓扑排序List<Integer> result = topologicalSort(V, adj);// 输出结果System.out.println("拓扑排序结果: " + result);}
}

算法比较

算法时间复杂度空间复杂度适用场景
Kahn's 算法 (BFS)O(V+E)O(V)适用于需要显式维护入度的场景
DFS 方法O(V+E)O(V)适用于需要递归深度优先搜索的场景

拓扑排序总结

  • Kahn's 算法:使用入度来逐步选出可以放入排序中的节点,适合广度优先遍历。
  • DFS 方法:递归访问图中的节点,后序遍历得到排序,适合深度优先遍历。
  • 有向无环图是拓扑排序的前提,如果图中存在环,则无法生成拓扑排序。

http://www.mrgr.cn/news/48401.html

相关文章:

  • ImportError: Install xlrd >= 1.0.0 for Excel support
  • 无需手动部署的正式版comfyUI是否就此收费?开源等同免费?
  • 5.Java入门笔记--数组
  • C# ref和out 有什么区别,分别用在那种场景
  • 下划线命名转驼峰
  • 014:无人机遥控器操作
  • 【小鹅通-登录/注册安全分析报告】
  • MES系统功能优势解析:如何提升生产管理水平
  • Qt消息对话框
  • 20241011-国庆在川西格聂徒步的杂记
  • springboot feign-httpclient 连接池配置
  • 使用shutil库实现文件复制和移动的实用指南
  • TypeScript中装饰器的理解
  • 【软件工程】详细说说什么是PERT图
  • AI学习指南深度学习篇-变分自编码器的应用与扩展
  • Maven 中央仓库地址推荐
  • 微信App支付申请遭拒怎么办
  • 月之暗面推出 Kimi 探索版:搜索量暴增 10 倍,精读 500 页信息,开启 AI 搜索新纪元
  • 79.【C语言】文件操作(4)
  • Matplotlib教程(002):Matplotlib基本图形绘制
  • 软件集成:守护核心——优化系统守护者,实时监测硬件健康
  • 蒙特卡罗方法 - 不同的峰值之间的混合挑战篇
  • 勇攀保研高峰:解锁环节与要点,更容易上岸成功
  • 【多线程】多线程(12):多线程环境下使用哈希表
  • Matplotlib教程(003):Matplotlib绘图画布配置
  • qt数据库的系统