算法与数据结构--有向图以及拓扑排序

发布时间:2023年12月18日

一.有向图基本概念

有向图是由一组顶点和一组有方向的边组成的。

出度:
由某个顶点指出的边的个数称为该顶点的出度。
入度:
指向某个顶点的边的个数称为该顶点的入度。
有向路径:
由一系列顶点组成,对于其中的每个顶点都存在一条有向边,从它指向序列中的下一个顶点。
有向环:
一条至少含有一条边,且起点和终点相同的有向路径。

二.拓扑排序

1.概念和我们为什么要用拓扑排序

给定一幅有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素,此时就可以明确的表示出每个顶点的优先级

2.应用场景

如:指定合理的学习方案

需要注意的是:拓扑排序适用于没有有向环的图

3.实现

参考教程:数据结构——拓扑排序和逆拓扑排序_哔哩哔哩_bilibili
拓扑排序!(自讲)_哔哩哔哩_bilibili

4.例题与代码(代办)

文章来源:https://blog.csdn.net/bjjx123456/article/details/134872385
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。