本文主要是介绍有向无权图最短路径问题——BFS求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解释
图1
如图1所示，这是一个有向无权图，如果选中某个定点作为起始顶点s，我们要找出s到其他所有顶点的最短路径问题。由于是无权的，所以我们只关心最短路径所包含的边数。这就是一个有向无权图求最短路径的问题，用到BFS算法，广义优先搜索算法。
流程解析
设s为选中的v3。
从s出发路径长为1的顶点之后的图
此时可以看到从s出发到v3的最短路径长为0的路径，只有v3自己。把这个标记下来。然后寻找所有从s出发路径长为1的顶点，这些顶点可以通过考察s邻接的顶点找到。
找出所有从s出发路径长为1的顶点之后的图
现在寻找从s出发，最短路径为2 的顶点，找出所有邻接到v1和v6的顶点（距离为1处的顶点）。它们的最短路径还不知道，这次搜索告诉我们，到v2和v4的最短路径长为2。下图显示了到目前为止所做的工作。
找出所有从s出发路径长为2的顶点之后的图
最后通过考察那些邻接到刚被赋值的v2和v4的顶点可以发现，v5和v7各有一
这篇关于有向无权图最短路径问题——BFS求解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
