算法BFS最短路径问题拓扑排序
【算法】BFS(最短路径问题、拓扑排序)
🌈个人主页：
🔥 系列专栏：
目录
前言
💬 hello! 各位铁子们大家好哇。
今日更新了最短路径问题和拓扑排序的相关内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
边权为1的最短路径问题
只要边权都是相同的，就可以看作是边权为1的最短路径问题。
上图中的数字就是权值，比如a和b之间的长度是3。最短路径问题就是从某个点到另外一个点的最短长度。最简单的最短路径问题，就是边权都为1的。
这里是一道例题： 题解在这：
多源BFS最短路问题
单源最短路问题就是只有一个起点和一个终点。
多源最短路问题是可以有多个起点和一个终点。
多源bfs：用bfs解决边权为1的多源最短路问题。
如上图，解法：把所有的源点当成一个“超级源点”。问题就变成单一的单源最短路问题。
绿色是源点（起点）。
例题： 题解：
BFS解决拓扑排序
有向无环图（DAG图）
如上图，由顶点和有方向的边连接起来的图，就是有向图。 ”无环“是指不会形成回路。
如上图，4指向5，5指向6，6又指向4，形成了一个环，此时就是有环的。
对于顶点的概念：
入度： 有多少条边指向该顶点
出度：由该顶点出去有几条边。
如上图，绿色代表入度，红色代表出度。1的入度是0，因为没有边指向它。1的出度是2，因为有两条边指向外面。
AOV网：顶点活动图
在有向无环图中，用顶点来表示一个活动，用边来表示活动的先后顺序的结构。
如上方的青椒炒肉工程图就是一个AOV网。
拓扑排序
拓扑排序简单来说，就是找到做事情的先后顺序，并且结果可能不能唯一的。
在这个工程图中，有些活动必须得在某些活动完成后才能执行。
如何排序？
最开始只能选择准备厨具或者买菜，他们两个其实都是入度为0的点。因此，活动的执行顺序其实就是把入度为0的点拿出来，然后把该点连接的边都删除，让别的点的入度减少。
操作：
1.找出图中入度为0的点，然后输出。
2.删除与该点连接的边。
3.重复1，2操作，直到图中没有点或者 没有入度为0 的点为止。
为什么要加上没有入度为0的点为循环结束条件呢？
因为我们并不知道图中是否有环。
所以拓扑排序有一个重要应用：判断有向图中是否有环。
实现拓扑排序
借助队列，进行一次bfs即可。
1.初始化：把所有入度为0的点加入到队列中
2.当队列不为空时：
1.拿出队头元素，加入到最终结果中；
2.删除与该元素相连的边；
3.判断：与删除边相连的点，是否入度变为0。如果入度为0，就加入到队列中。
例题： 题解：