BFS在算法中的应用：最短路径与拓扑排序解析
目录
- 边权为1的最短路径问题
- 多源BFS最短路问题
- BFS解决拓扑排序
- 有向无环图（DAG图）
- AOV网：顶点活动图
- 拓扑排序
- 实现拓扑排序
前言
大家好呀！今天为大家带来关于最短路径以及拓扑排序的相关内容，欢迎大家关注、点赞、收藏并留言交流哦。
边权为1的最短路径问题
当所有边的权重都相同时，这类情况可视为边权为1的最短路径问题。就像图中所示的数字代表权重，例如a与b之间的长度是3，而最短路径问题聚焦于从一个点到另一个点的最短距离，其中边权均为1的情况是最为基础的。
这里有一道例题：. - 力扣（LeetCode） 题解在这： . - 力扣（LeetCode）
多源BFS最短路问题
单源最短路径问题指的是仅有一个起始点和一个终点的情况。而多源最短路径问题则允许存在多个起始点，但仅有一个终点。多源广度优先搜索（BFS）可用于解决边权为1的多源最短路径问题。例如图中的解法是将所有源点当作一个‘超级源点’，如此便将问题转化为单一的单源最短路径问题，图中的绿色部分即为源点（起点）。
例题：. - 力扣（LeetCode） 题解：. - 力扣（LeetCode）
BFS解决拓扑排序
有向无环图（DAG图）
由顶点以及带有方向的边连接而成的图被称作有向图。所谓‘无环’，意味着不会出现回路。就像图中所示，4指向5，5指向6，而6又指向4，这样就形成了一个环，此时便是有环的情况。关于顶点的相关概念：入度指的是有多少条边指向该顶点；出度则是由该顶点出发的边的数量。例如图中绿色部分表示入度，红色部分表示出度，顶点1的入度为0，这是因为没有边指向它，而顶点1的出度为2，是由于有两条边从它出发指向外部。
AOV网：顶点活动图
在有向无环图中，利用顶点来代表一项活动，并用边来体现活动之间先后顺序的结构即为AOV网，就像上方的青椒炒肉工程图所展示的那样。
拓扑排序
拓扑排序简单来讲，是去探寻事情开展的先后顺序，而且结果有可能并非唯一。在这个工程图里，某些活动必须得在另外一些活动完成之后才能进行。那该如何进行排序呢？最开始的时候只能选择准备厨具或者买菜，这两者其实都是入度为0的节点。所以，活动的执行顺序实际上是把入度为0的节点找出来并输出，接着删除与该节点相连的边，让其他节点的入度随之减少，然后重复这个过程，直到图中没有节点或者不存在入度为0的节点为止。之所以要把不存在入度为0的节点作为循环结束的条件，是因为我们无法预先知晓图中是否存在环。所以拓扑排序有一个重要的用途，就是用来判断有向图中是否存在环。
实现拓扑排序
借助队列来进行一次广度优先搜索（BFS）就能实现。具体步骤为：首先进行初始化，把所有入度为0的节点加入到队列当中。当队列不为空时，执行以下操作：取出队头元素，并将其加入到最终的结果集合里；删除与该元素相连的边；然后判断与被删除边相连的节点，其入度是否变为了0，如果变为了0，就把该节点加入到队列中。
例题：. - 力扣（LeetCode） 题解：. - 力扣（LeetCode）
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/12978.html
