算法与数据结构--有向图以及拓扑排序
发布时间:2023年12月18日
一.有向图基本概念
有向图是由一组顶点和一组有方向的边组成的。
出度:
由某个顶点指出的边的个数称为该顶点的出度。
入度:
指向某个顶点的边的个数称为该顶点的入度。
有向路径:
由一系列顶点组成,对于其中的每个顶点都存在一条有向边,从它指向序列中的下一个顶点。
有向环:
一条至少含有一条边,且起点和终点相同的有向路径。
二.拓扑排序
1.概念和我们为什么要用拓扑排序
给定一幅有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素,此时就可以明确的表示出每个顶点的优先级。
2.应用场景
如:指定合理的学习方案
需要注意的是:拓扑排序适用于没有有向环的图。
3.实现
参考教程:数据结构——拓扑排序和逆拓扑排序_哔哩哔哩_bilibili
拓扑排序!(自讲)_哔哩哔哩_bilibili
4.例题与代码(代办)
文章来源:https://blog.csdn.net/bjjx123456/article/details/134872385
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:chenni525@qq.com进行投诉反馈,一经查实,立即删除!