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

2023-12-14 13:13:30

一.有向图基本概念

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

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

二.拓扑排序

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

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

2.应用场景

如：指定合理的学习方案

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

3.实现

参考教程：数据结构——拓扑排序和逆拓扑排序_哔哩哔哩_bilibili
拓扑排序！（自讲）_哔哩哔哩_bilibili

4.例题与代码（代办）

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