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

拓扑排序与有向无环图 -- Kahn算法和深度优先搜索

拓扑排序与有向无环图

文章目录

  • 拓扑排序与有向无环图
    • 1. 什么是拓扑排序
      • 快速排序(Quick Sort)
      • 拓扑排序(Topological Sort)
      • 主要区别
    • 2. 拓扑排序与有向无环图之间的契合性
    • 3. Kahn算法实现拓扑排序
      • 算法思想
      • 算法步骤
      • 算法代码
    • 4. 深度优先搜索(DFS)实现拓扑排序
      • 算法思想
      • 算法步骤
      • 算法代码
    • 5. 总结

1. 什么是拓扑排序

核心思想:根据节点之间的依赖关系进行排序

拓扑排序并非等同于快排等常见算法的应用场景,下面对其进行对比以便明晰拓扑排序的使用场景和排序目的:

快速排序(Quick Sort)

  • 目的对一组数按大小顺序进行排序
  • 应用场景:用于对无序数组进行排序,使得数组中的元素按升序或降序排列。
  • 算法思想:通过选择一个基准元素,将数组分成两部分,一部分小于基准元素,另一部分大于基准元素,然后递归地对这两部分进行排序。

拓扑排序(Topological Sort)

  • 目的对有向无环图(DAG)中的节点进行排序,使得对于每一条有向边 ( u -> v ),节点 ( u ) 在排序结果中出现在节点 ( v ) 之前。
  • 应用场景:用于表示依赖关系的场景,例如任务调度、课程安排、编译顺序等。
  • 算法思想通过不断移除入度为0的节点,构建一个线性序列,使得每个节点都在其所有前驱节点之后。

主要区别

  • 数据结构:快排处理的是数组或列表,而拓扑排序处理的是有向无环图
  • 排序依据:快排根据元素的大小进行排序,而拓扑排序根据图中的依赖关系进行排序。
  • 结果:快排的结果是一个按大小顺序排列的数组,而拓扑排序的结果是一个满足依赖关系的节点序列

2. 拓扑排序与有向无环图之间的契合性

  1. 依赖关系:在有向无环图中,每条有向边 ( u -> v ) 表示节点 ( u ) 是节点 ( v ) 的前驱,或者说 ( v ) 依赖于 ( u )。拓扑排序的目标是找到一个线性序列,使得每个节点都在其所有前驱节点之后。
  2. 无环性:如果图中存在环,那么就无法找到一个满足所有依赖关系的线性序列。例如,如果存在一个环 ( u -> v -> w ->u ),那么 ( u ) 既需要在 ( v ) 之前,又需要在 ( v ) 之后,这是不可能的。

3. Kahn算法实现拓扑排序

算法思想

Kahn算法的核心思想是通过不断移除入度为0的节点来实现拓扑排序。核心步骤如下:

  1. 入度为0的节点:在有向无环图(DAG)中,入度为0的节点是没有任何前驱节点的节点。这些节点可以作为拓扑排序的起点。
  2. 移除节点:将入度为0的节点从图中移除,并将其加入拓扑排序结果中。然后,更新其所有邻接节点的入度。
  3. 重复过程:重复上述过程,直到所有节点都被移除。如果在某个时刻没有入度为0的节点,但仍有节点未被移除,则说明图中存在环,无法进行拓扑排序。

算法步骤

  1. 读取输入
    • 读取点的个数 ( n ) 和边的条数 ( m )。
    • 初始化一个邻接表 graph 和一个入度数组 in_degree,用于存储每个节点的入度。
  2. 构建图和入度数组
    • 读取每条边的信息,并更新邻接表和入度数组。
    • 邻接表 graph[u] 存储从节点 ( u ) 出发的所有边的终点。
    • 入度数组 in_degree[v] 记录节点 ( v ) 的入度,即有多少条边指向 ( v )。
  3. 初始化队列
    • 创建一个队列 q,用于存储所有入度为0的节点。
    • 遍历所有节点,将入度为0的节点加入队列。
  4. 拓扑排序
    • 创建一个向量 topo_order,用于存储拓扑排序结果。
    • 当队列不为空时,执行以下操作:
      • 从队列中取出一个节点 node,将其加入 topo_order
      • 遍历 node 的所有邻接节点 neighbor,将这些邻接节点的入度减1。
      • 如果某个邻接节点的入度变为0,则将其加入队列。
  5. 检查结果
    • 如果 topo_order 的大小等于节点数 ( n ),则输出拓扑排序结果。
    • 否则,输出 -1,表示图中存在环,无法进行拓扑排序。

算法代码

// 假定有如下题目:
/*
给定一个包含 n 个点 m 条边的有向无环图,求出该图的拓扑序。若图的拓扑序不唯一,输出任意合法的拓扑序即可。若该图不能拓扑排序,输出-1。
输入描述:
第一行输入两个整数 n,m(1≤n,m<2·10^5),表示点的个数和边的条数。
接下来的 m 行,每行输入两个整数 Ui,Vi(1≤u,v≤n),表示 Ui 到 Vi 之间有一条有向边。
输出描述:
若图存在拓扑序,输出一行 n 个整数,表示拓扑序。否则输出 -1。
*/#include <iostream>
#include <vector>
#include <queue>int main() {int n, m;std::cin >> n >> m;std::vector<std::vector<int>> graph(n + 1);std::vector<int> in_degree(n + 1, 0);// 读取边并构建图和入度数组for (int i = 0; i < m; ++i) {int u, v;std::cin >> u >> v;graph[u].push_back(v);in_degree[v]++;}std::queue<int> q;// 将所有入度为0的节点加入队列for (int i = 1; i <= n; ++i) {if (in_degree[i] == 0) {q.push(i);}}std::vector<int> topo_order;while (!q.empty()) {int node = q.front();q.pop();topo_order.push_back(node);// 遍历当前节点的所有邻接节点for (int neighbor : graph[node]) {in_degree[neighbor]--;if (in_degree[neighbor] == 0) {q.push(neighbor);}}}// 检查是否所有节点都被排序if (topo_order.size() == n) {for (int i = 0; i < n; ++i) {std::cout << topo_order[i] << " ";}std::cout << std::endl;} else {std::cout << -1 << std::endl;}return 0;
}

4. 深度优先搜索(DFS)实现拓扑排序

算法思想

DFS方法的核心思想是利用递归的回溯特性,在回溯时将节点加入拓扑排序结果中。这样可以确保每个节点都在其所有后继节点之前被处理。通过这种方式,DFS能够有效地找到一个合法的拓扑排序,或者检测到图中是否存在环。

算法步骤

  1. 读取输入
    • 读取点的个数 ( n ) 和边的条数 ( m )。
    • 初始化一个邻接表 graph 和一个访问标记数组 visited
  2. 构建图
    • 读取每条边的信息,并更新邻接表 graph
  3. 深度优先搜索
    • 对每个未访问的节点调用DFS函数。
    • 在DFS过程中,递归访问所有邻接节点。
    • 在回溯时,将当前节点压入栈 topo_stack
  4. 输出结果
    • 检查栈中的节点数是否等于 ( n )。如果不等于,说明图中存在环,无法进行拓扑排序,输出 -1。
    • 否则,依次弹出栈中的节点,输出拓扑排序结果。

算法代码

// 假定有如下题目:
/*
给定一个包含 n 个点 m 条边的有向无环图,求出该图的拓扑序。若图的拓扑序不唯一,输出任意合法的拓扑序即可。若该图不能拓扑排序,输出-1。
输入描述:
第一行输入两个整数 n,m(1≤n,m<2·10^5),表示点的个数和边的条数。
接下来的 m 行,每行输入两个整数 Ui,Vi(1≤u,v≤n),表示 Ui 到 Vi 之间有一条有向边。
输出描述:
若图存在拓扑序,输出一行 n 个整数,表示拓扑序。否则输出 -1。
*/#include <iostream>
#include <vector>
#include <stack>void dfs(int node, const std::vector<std::vector<int>>& graph, std::vector<bool>& visited, std::stack<int>& topo_stack) {visited[node] = true;for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor, graph, visited, topo_stack);}}topo_stack.push(node);
}int main() {int n, m;std::cin >> n >> m;std::vector<std::vector<int>> graph(n + 1);std::vector<bool> visited(n + 1, false);std::stack<int> topo_stack;// 读取边并构建图for (int i = 0; i < m; ++i) {int u, v;std::cin >> u >> v;graph[u].push_back(v);}// 对每个节点进行DFSfor (int i = 1; i <= n; ++i) {if (!visited[i]) {dfs(i, graph, visited, topo_stack);}}// 检查是否所有节点都被访问if (topo_stack.size() != n) {std::cout << -1 << std::endl;} else {// 输出拓扑排序结果while (!topo_stack.empty()) {std::cout << topo_stack.top() << " ";topo_stack.pop();}std::cout << std::endl;}return 0;
}

5. 总结

拓扑排序是一种用于有向无环图(DAG)的排序算法,旨在根据节点之间的依赖关系生成一个线性序列。本文详细介绍了两种实现拓扑排序的方法:Kahn算法和深度优先搜索(DFS)Kahn算法通过不断移除入度为0的节点来实现排序,而DFS方法利用递归的回溯特性在回溯时将节点加入排序结果中。两种方法都能有效地检测图中是否存在环,并生成合法的拓扑排序。

相关文章:

  • 北京网站建设多少钱?
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Redis - SpringDataRedis - RedisTemplate
  • QT Creator下载安装详细教程(保姆级教程)
  • NCRE3 2-1 网络总体设计基本方法
  • 如何使用 API 查看极狐GitLab 镜像仓库中的镜像?
  • Flutter Geocoding插件使用指南:简化地理编码与逆地理编码
  • Redis与MySQL数据一致性问题的策略模式及解决方案
  • 如何从网站获取表格数据
  • 第四十八天 第十章 单调栈part01 739. 每日温度 496.下一个更大元素 I 503.下一个更大元素II
  • TypeScript通过MsgPack发送数组到C++反序列化失败
  • 前端播放rtsp视频流(最后使用WebRtc)
  • MySQL环境的配置文件json
  • Redis zset 共享对象
  • OpenSNN推文:百度沈抖:深度拥抱人工智能+,加速发展新质生产力,共创智能时代新未来
  • 故障诊断 | 基于Transformer故障诊断分类预测(Matlab)
  • Godot入门 03世界构建1.0版
  • -------------------- 第二讲-------- 第一节------在此给出链表的基本操作
  • [微信小程序] 使用ES6特性Class后出现编译异常
  • [译] 理解数组在 PHP 内部的实现(给PHP开发者的PHP源码-第四部分)
  • 「前端早读君006」移动开发必备:那些玩转H5的小技巧
  • exif信息对照
  • Java 9 被无情抛弃,Java 8 直接升级到 Java 10!!
  • jQuery(一)
  • JS变量作用域
  • 阿里云爬虫风险管理产品商业化,为云端流量保驾护航
  • 设计模式 开闭原则
  • 微信公众号开发小记——5.python微信红包
  • 我的面试准备过程--容器(更新中)
  • 由插件封装引出的一丢丢思考
  • 做一名精致的JavaScripter 01:JavaScript简介
  • nb
  • [Shell 脚本] 备份网站文件至OSS服务(纯shell脚本无sdk) ...
  • Java性能优化之JVM GC(垃圾回收机制)
  • 京东物流联手山西图灵打造智能供应链,让阅读更有趣 ...
  • 如何用纯 CSS 创作一个货车 loader
  • # 数论-逆元
  • #1015 : KMP算法
  • ${ }的特别功能
  • (a /b)*c的值
  • (zhuan) 一些RL的文献(及笔记)
  • (二)hibernate配置管理
  • (二十五)admin-boot项目之集成消息队列Rabbitmq
  • (附源码)springboot宠物管理系统 毕业设计 121654
  • (附源码)springboot家庭财务分析系统 毕业设计641323
  • (原創) 人會胖會瘦,都是自我要求的結果 (日記)
  • (转)C#调用WebService 基础
  • (转)Oracle存储过程编写经验和优化措施
  • (转)甲方乙方——赵民谈找工作
  • (转)利用ant在Mac 下自动化打包签名Android程序
  • (转)淘淘商城系列——使用Spring来管理Redis单机版和集群版
  • .dat文件写入byte类型数组_用Python从Abaqus导出txt、dat数据
  • .NET 动态调用WebService + WSE + UsernameToken
  • .NET 中创建支持集合初始化器的类型
  • .NET 中小心嵌套等待的 Task,它可能会耗尽你线程池的现有资源,出现类似死锁的情况
  • .NET/C# 阻止屏幕关闭,阻止系统进入睡眠状态
  • .net打印*三角形