拓扑排序:Kahn算法与DFS算法
引言
拓扑排序是有向无环图(DAG)中的一种线性排序,使得对于图中的每一条有向边 ( u \rightarrow v ),顶点 ( u ) 在排序中出现在顶点 ( v ) 之前。本文将详细介绍两种实现拓扑排序的算法:Kahn算法和基于深度优先搜索(DFS)的算法。
目录
- Kahn算法
- 基于DFS的算法
Kahn算法
定义
Kahn算法是一种基于入度的拓扑排序算法。该算法通过不断移除入度为0的顶点及其边来构建拓扑排序。
算法步骤
- 初始化:计算图中所有顶点的入度,并将所有入度为0的顶点添加到一个队列中。
- 构建排序:从队列中取出一个顶点,将其添加到拓扑排序的结果中,并移除该顶点及其所有出边。对于每个被移除的出边,如果目标顶点的入度减为0,则将该顶点添加到队列中。
- 检测环:重复步骤2,直到队列为空。如果排序结果中的顶点数量小于图中的顶点数量,则说明图中存在环,无法进行拓扑排序。
示例
假设我们有一个有向无环图,顶点集合为 ({A, B, C, D, E, F}),边集合为 ({(A, C), (B, C), (B, D), (C, E), (D, F), (E, F)})。
Kahn算法实现
下面是用Java实现Kahn算法的代码示例:
import java.util.*;public class KahnAlgorithm {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public KahnAlgorithm(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}// 添加边public void addEdge(int src, int dest) {adjList[src].add(dest);}// Kahn算法实现的拓扑排序public void topologicalSort() {int[] inDegree = new int[vertices];for (int i = 0; i < vertices; i++) {for (int dest : adjList[i]) {inDegree[dest]++;}}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < vertices; i++) {if (inDegree[i] == 0) {queue.add(i);}}List<Integer> topOrder = new ArrayList<>();while (!queue.isEmpty()) {int u = queue.poll();topOrder.add(u);for (int neighbor : adjList[u]) {if (--inDegree[neighbor] == 0) {queue.add(neighbor);}}}if (topOrder.size() != vertices) {System.out.println("图中存在环,无法进行拓扑排序");return;}System.out.println("拓扑排序结果:");for (int node : topOrder) {System.out.print(node + " ");}}public static void main(String[] args) {KahnAlgorithm graph = new KahnAlgorithm(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();}
}
代码注释
-
类和构造函数:
public class KahnAlgorithm {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public KahnAlgorithm(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}
KahnAlgorithm
类包含图的顶点数量和邻接表,并有一个构造函数来初始化这些变量。 -
添加边:
public void addEdge(int src, int dest) {adjList[src].add(dest); }
addEdge
方法用于向图中添加边。 -
Kahn算法的拓扑排序:
public void topologicalSort() {int[] inDegree = new int[vertices];for (int i = 0; i < vertices; i++) {for (int dest : adjList[i]) {inDegree[dest]++;}}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < vertices; i++) {if (inDegree[i] == 0) {queue.add(i);}}List<Integer> topOrder = new ArrayList<>();while (!queue.isEmpty()) {int u = queue.poll();topOrder.add(u);for (int neighbor : adjList[u]) {if (--inDegree[neighbor] == 0) {queue.add(neighbor);}}}if (topOrder.size() != vertices) {System.out.println("图中存在环,无法进行拓扑排序");return;}System.out.println("拓扑排序结果:");for (int node : topOrder) {System.out.print(node + " ");} }
topologicalSort
方法实现了Kahn算法,进行拓扑排序。 -
主函数:
public static void main(String[] args) {KahnAlgorithm graph = new KahnAlgorithm(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort(); }
main
方法创建一个图并进行拓扑排序。
Kahn算法的执行过程图解
基于DFS的算法
定义
基于DFS的拓扑排序算法通过递归的方式遍历图的每个顶点,并在访问完所有邻接顶点后将顶点压入栈中,最终从栈顶依次弹出顶点即为拓扑排序结果。
算法步骤
- 初始化:创建一个栈用于存储排序结果,标记所有顶点为未访问。
- DFS遍历:对于每个未访问的顶点,进行DFS遍历。递归访问该顶点的所有邻接顶点,访问完毕后将该顶点压入栈中。
- 构建排序:重复步骤2,直到所有顶点都被访问。最后从栈顶
依次弹出顶点即为拓扑排序结果。
示例
假设我们有一个有向无环图,顶点集合为 ({A, B, C, D, E, F}),边集合为 ({(A, C), (B, C), (B, D), (C, E), (D, F), (E, F)})。
基于DFS的算法实现
下面是用Java实现基于DFS的拓扑排序算法的代码示例:
import java.util.*;public class DFSTopologicalSort {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public DFSTopologicalSort(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}// 添加边public void addEdge(int src, int dest) {adjList[src].add(dest);}// 递归实现DFSprivate void DFS(int vertex, boolean[] visited, Stack<Integer> stack) {visited[vertex] = true;for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {DFS(neighbor, visited, stack);}}stack.push(vertex);}// 基于DFS的拓扑排序public void topologicalSort() {Stack<Integer> stack = new Stack<>();boolean[] visited = new boolean[vertices];for (int i = 0; i < vertices; i++) {if (!visited[i]) {DFS(i, visited, stack);}}System.out.println("拓扑排序结果:");while (!stack.isEmpty()) {System.out.print(stack.pop() + " ");}}public static void main(String[] args) {DFSTopologicalSort graph = new DFSTopologicalSort(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort();}
}
代码注释
-
类和构造函数:
public class DFSTopologicalSort {private int vertices; // 顶点数量private List<Integer>[] adjList; // 邻接表public DFSTopologicalSort(int vertices) {this.vertices = vertices;adjList = new List[vertices];for (int i = 0; i < vertices; i++) {adjList[i] = new ArrayList<>();}}
DFSTopologicalSort
类包含图的顶点数量和邻接表,并有一个构造函数来初始化这些变量。 -
添加边:
public void addEdge(int src, int dest) {adjList[src].add(dest); }
addEdge
方法用于向图中添加边。 -
递归实现DFS:
private void DFS(int vertex, boolean[] visited, Stack<Integer> stack) {visited[vertex] = true;for (int neighbor : adjList[vertex]) {if (!visited[neighbor]) {DFS(neighbor, visited, stack);}}stack.push(vertex); }
DFS
方法递归访问顶点及其邻接顶点,并在访问完所有邻接顶点后将顶点压入栈中。 -
基于DFS的拓扑排序:
public void topologicalSort() {Stack<Integer> stack = new Stack<>();boolean[] visited = new boolean[vertices];for (int i = 0; i < vertices; i++) {if (!visited[i]) {DFS(i, visited, stack);}}System.out.println("拓扑排序结果:");while (!stack.isEmpty()) {System.out.print(stack.pop() + " ");} }
topologicalSort
方法实现了基于DFS的拓扑排序,输出拓扑排序结果。 -
主函数:
public static void main(String[] args) {DFSTopologicalSort graph = new DFSTopologicalSort(6);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(2, 4);graph.addEdge(3, 5);graph.addEdge(4, 5);graph.topologicalSort(); }
main
方法创建一个图并进行拓扑排序。
基于DFS算法的执行过程图解
结论
通过上述讲解和实例代码,我们详细展示了Kahn算法和基于DFS的拓扑排序算法的定义、步骤及其实现。希望这篇博客对您有所帮助!
如果您觉得这篇文章对您有帮助,请关注我的CSDN博客,点赞并收藏这篇文章,您的支持是我持续创作的动力!
关键内容总结:
- Kahn算法的定义和实现
- 基于DFS的拓扑排序算法的定义和实现
- 两种算法的执行过程图解
推荐阅读:深入探索设计模式专栏,详细讲解各种设计模式的应用和优化。点击查看:深入探索设计模式。
特别推荐:设计模式实战专栏,深入解析设计模式的实际应用,提升您的编程技巧。点击查看:设计模式实战。
如有任何疑问或建议,欢迎在评论区留言讨论。谢谢阅读!
相关文章:
拓扑排序:Kahn算法与DFS算法
引言 拓扑排序是有向无环图(DAG)中的一种线性排序,使得对于图中的每一条有向边 ( u \rightarrow v ),顶点 ( u ) 在排序中出现在顶点 ( v ) 之前。本文将详细介绍两种实现拓扑排序的算法:Kahn算法和基于深度优先搜索&…...
图像处理 -- Sobel滤波器的实现原理与使用案例
Sobel滤波器 概述 Sobel滤波器是一种边缘检测方法,用于图像处理和计算机视觉领域。它通过计算图像灰度值的梯度来检测边缘。Sobel滤波器结合了高斯平滑和微分操作,以减少噪声并增强边缘检测效果。 实现原理 Sobel滤波器通过使用两个3x3卷积核&#x…...

机器学习 第10章-降维与度量学习
机器学习 第10章-降维与度量学习 10.1 k近邻学习 k近邻(k-Nearest Neighbor,简称kNN)学习是一种常用的监督学习方法其工作机制非常简单:给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测。通…...
linux驱动:(7)物理地址到虚拟地址映射
单片机、裸机、linux操控硬件方法 在单片机和裸机中操作硬件是通过指针来对寄存器赋值来进行操控 但对于linux中不能这样,不能直接对物理地址直接修改,因为linux使能了mmu,所以不能直接菜操作物理地址 如果要操作硬件,需要先把…...

浏览器用户文件夹详解 - Preferences(十)
1.Preferences简介 1.1 什么是Preferences文件? Preferences文件是Chromium浏览器中用于存储用户个性化设置和配置的一个重要文件。每当用户在浏览器中更改设置或安装扩展程序时,这些信息都会被记录在Preferences文件中。通过这些记录,浏览…...
Robot Operating System——电池电量通知
大纲 应用场景定义字段解释 案例 sensor_msgs::msg::BatteryState 是 ROS 2 中定义的消息类型,用于表示电池状态。它包含了电池电量、电压、电流、温度等信息。 应用场景 机器人 电池监控:在移动机器人中,电池是主要的电源。BatteryState 消…...
二进制安装docker
目录 一、准备 Docker CE 二进制包 二、解压.tgz包 三、复制二进制文件到/usr/bin/目录 四、创建用户组 五、配置相关服务配置文件 六、拷贝配置文件到指定目录 七、启动 dockerd 服务进程 八、shell脚本一键安装 一、准备 Docker CE 二进制包 https://download.docker…...
@SpringBootConfiguration重复加载报错
Junit单元测试Test启动报错,SpringBootConfiguration注解重复问题排查: SpringBootApplication 注解的 exclude 属性用于排除特定的自动配置类,而不是用于排除主配置类本身。因此,不能通过 exclude 属性来排除主配置类的加载。 …...
【SpringBoot】数据验证之分组校验
分组校验 在不同情况下,可能对JavaBean对象的数据校验规则有所不同,有时需要根据数据状态对JavaBean中的某些属性字段进行单独验证。这时就可以使用分组校验功能,即根据状态启用一组约束。 Hibernate Validator的注解提供了groups参数&#…...

MySQL Galera Cluster 部署与介绍
目录 主要特点 组件 一. 环境准备 二. 配置 1. 配置 galera1 主机的my.cnf的文件 2. 配置 galera2 主机的my.cnf的文件 3. 配置 galera3 主机的my.cnf的文件 4. 在给galera1 主机的my.cnf的文件增加节点 5. 写入数据验证同步 6. 配置 galera4 主机的my.cnf的文件 M…...

RuoYi-Vue-Plus (XXL-JOB任务调度中心二:配置管理与定时任务编写、执行策略、命令行任务、邮件报警等等
一、后端xxl job的配置属性介绍 enabled : 是否开启执行器,如果为false,调度中心就调用不了后端定时任务admin-addresses:调度中心的地址,多个则可以逗号拼接: url1,url2,url3access-token: 执行器通讯TOKEN ,必须和x…...

【docker】虚拟化与docker基础
一、虚拟化 1.虚拟化概述 什么是虚拟化? 虚拟化:将应用程序和系统内核资源进行解耦,以操作系统级别进行隔离,目的是提高资源利用率 2、虚拟化的功能 将虚拟化的性能优化趋近于物理资源的性能,主要用于提高资源利用…...

Vue3安装ffmpeg做视频截取报错
通过 yarn 安装 ffmpeg 时报错。 即,执行以下指令时报错: yarn add ffmpeg/ffmpeg^0.10.0 yarn add ffmpeg/core^0.10.0错误信息: node_modules\pngquant-bin: Command failed. Error: pngquant failed to build, make sure that libpng-d…...
如何在 Java 中实现自定义的排序算法?
在Java中实现自定义排序算法的步骤如下: 创建一个类,实现Java的Comparator接口,该接口包含一个compare方法,用于比较两个对象的大小。在compare方法中,根据自定义的排序规则,比较两个对象的大小并返回-1、…...
【Homebrew】brew 命令
Brew(也称为Homebrew)是Mac OS上的一款包管理器,它允许用户通过简单的命令行界面来安装、更新、卸载和管理软件包。以下是一些常用的Brew命令及其功能说明: 安装与卸载 安装Brew 命令(适用于大多数用户,可…...
【https】无法安装OpenSSL时如何在局域网开通https服务
【背景】 做Stream传输服务,需要用到fetch方法,所以自然也需要https服务。 公司的开发机由于某些管理上的原因无法直接安装openssl for win的安装包。 【分析】 没有命令行工具,就试试看万能的python包吧,直接安装cryptography包。 pip install cryptography【方法】 …...

OpenGL实现3D游戏编程【连载1】——初探3D世界
1、前言 在我学习C的过程中,研究了一下OpenGL编程,打开了3D世界的编程世界,3D世界的效果还是相当不错。而且OpenGL能够支持跨平台兼容,是不错的学习方向,于是就自己学习了网上的很多教程,并将所有学到的知…...

工程化实践:工程配置化设计
文内项目 Github:XIAOJUSURVEY 配置化是很灵活且很常见的使用,那XIAOJUSURVEY里有哪些地方应用到了呢? 基础模板 问卷模板 在创建问卷时,我们提供了多种问卷类型选择,例如普通问卷、投票、报名、NPS等。 为了实…...

浏览器事件循环详解
1. 浏览器的进程模型 1.1. 何为进程? 程序运行需要有它自己的专属内存空间,可以把这块内存空间简单的理解为进程。 每个应用至少有一个进程,进程之间相互独立,即使要通信,也需要双方同意。 1.2. 何为线程?…...
Linux:线程管理(线程创建、线程退出、线程回收、线程分离、其它线程函数)
线程管理 (1)What(什么是线程管理) 对程序中线程的创建、调度、同步、退出、回收等操作进行有效的控制和协调 (2)Why(为什么要管理线程) 充分利用系统资源,提高程序的并发的性能和稳定性。但如果管理不当,…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...