【算法】BFS(最短路径题目、拓扑排序)

🌈个人主页：秦jh_-CSDN博客
🔥 系列专栏：
 

​ 

目次
边权为1的最短路径题目
 多源BFS最短路题目
BFS办理拓扑排序
有向无环图（DAG图）
AOV网：极点运动图
拓扑排序
 实现拓扑排序

---

媒介

       💬 hello! 各位铁子们各人好哇。
               本日更新了最短路径题目和拓扑排序的相干内容
    🎉 欢迎各人关注🔍点赞👍收藏⭐️留言📝
  边权为1的最短路径题目

只要边权都是类似的，就可以看作是边权为1的最短路径题目。

   上图中的数字就是权值，比如a和b之间的长度是3。最短路径题目就是从某个点到别的一个点的最短长度。最简朴的最短路径题目，就是边权都为1的。 
  这里是一道例题：. - 力扣（LeetCode）  题解在这：  . - 力扣（LeetCode）
 多源BFS最短路题目

单源最短路题目就是只有一个出发点和一个尽头。
多源最短路题目是可以有多个出发点和一个尽头。
多源bfs：用bfs办理边权为1的多源最短路题目。

   如上图，解法：把全部的源点当成一个“超等源点”。题目就变成单一的单源最短路题目。
  绿色是源点（出发点）。
  例题：. - 力扣（LeetCode）    题解：. - 力扣（LeetCode）
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，就到场到队列中。
例题：. - 力扣（LeetCode）   题解：. - 力扣（LeetCode）