拓扑排序
2023-03-14 09:44:39 时间
一、定义:
没有圈的有向图,叫做DAG(Directed Acyclic Graph,有向无环图)
拓扑排序定义:将DAG中的顶点以线性方式进行排序。即对于任何自顶点u到顶点v的有向边u->v,在最后的排序结果中,顶点u总是在顶点v的前面。这样的排序结果,称为拓扑序。有环图,不存在拓扑排序。
二、拓扑排序具体的应用
三、代码实现
这份代码还有判断是否有环的功能。
1 /*具有检测是否有环的功能*/ 2 public class 图的dfs_拓扑排序 { 3 // 顶点数 4 static final int n = 4; 5 // 顶点内容 6 static String[] v = { "a", "b", "c", "d" }; 7 // 有向图的邻接矩阵表示法 8 static int[][] graph = { { 0, 1, 0, 0 }, { 0, 0, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 1, 0 }, }; 9 // 标记顶点访问状态,1:已经访问并返回,0:从未被方位,-1:正在递归访问还未退出 10 static int[] vis = new int[n]; 11 // 拓扑排序结果 12 static int[] topo = new int[n]; 13 // 标记topo数组的哪一位被改写 14 static int t = n; 15 16 public static void main(String[] args) { 17 // 对所有顶点进行迭代 18 for (int i = 0; i < n; i++) { 19 // 如果被访问,则跳过 20 if (vis[i] == 1) 21 continue; 22 23 boolean bool = dfs(i);// 是否有拓扑序 24 if (!bool) { 25 System.out.println(false); 26 return; 27 } 28 } 29 for (int i = 0; i < n; i++) { 30 System.out.println(v[topo[i]]); // 输出 d c a b 31 } 32 } 33 34 private static boolean dfs(int i) { 35 vis[i] = -1; 36 //遍历所有顶点 37 for (int j = 0; j < n; j++) { 38 if (graph[i][j] > 0) {//当前关注顶点i到顶点j有出度 39 //此处,关于j顶点的递归还没有退出,前驱的状态是-1,后继的状态也是-1,说明在此次递归的链路上早就路过了j,现在是第二次路过j, 40 // 一次递归链路两次经过j,只有一种情况,形成了环 41 if (vis[j] < 0) return false; 42 //j没被访问过,执行递归 43 if (vis[j] == 0 && dfs(j) == false) return false; 44 } 45 } 46 //整个递归是按照出度方向来的,所以上面的循环+递归走到尽头时,i没有出度,没有出度的点可以认为是最大的点(之一) 47 topo[--t] = i; 48 vis[i] = 1; 49 return true; 50 } 51 }
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的