数据结构导论之拓扑排序

简介: 数据结构导论之拓扑排序

概念

       设G=(V,E)是一个具有n个顶点的有向图,V中顶点的序列v1,v2,……,vn称为一个拓扑序列,且当仅当该顶点序列满足下列条件:在有向图G中,从顶点vi到vj有一条路径,则在拓扑序列中顶点vi必须排在顶点vj之前,找一个有向图的一个拓扑序列的过程称为拓扑序列。

步骤

       1.从图中选择一个入度为0的顶点,输出该顶点。

       2.从图中删除该顶点以及相关联的弧,调整被删弧的弧头节点的入度。

       3.重复执行1和2步骤直到所有入度为0的顶点都被输出,拓扑排序完成,或者图中没有入度为0的顶点。

20210828094720100.jpg图中的拓扑排序的步骤为:C1,C2,C5,C4,C3

总结

       1.先找入度为0的结点,而不是默认从V0或者1出发

       2.任何一个无环有向图,其全部顶点可以排成一个拓扑序列

       3.从一个顶点能访问其他所有的顶点


相关文章
|
2月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
34 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
2月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
29 1
|
2月前
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(二)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
2月前
|
搜索推荐 C++
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(一)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
2月前
|
算法
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
|
2月前
|
人工智能 搜索推荐 算法
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理(三)
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
|
4月前
|
C语言
数据结构——排序【上】
数据结构——排序【上】
|
4月前
|
搜索推荐 算法 测试技术
【数据结构】排序
【数据结构】排序
|
5月前
|
搜索推荐
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】
【数据结构常见七大排序(三)上】—交换排序篇【冒泡排序】And【快速排序】