本文共 1306 字，大约阅读时间需要 4 分钟。

---

解释

图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各有一条三边的最短路径。现在所有顶点都已经计算。下图显示最终的算法结果。

上述搜索方法称为广度优先搜索(breadth first search）。该方法是按层处理顶点：距开始点最近的那些顶点首先被求值，而最远的那些顶点最后被求值。这很像对数的层序遍历(level order traversal）。

下图是用于求无权最短路径计算的表的初始配置

对于每个顶点，我们需要跟踪三个信息。known表示该顶点是否被处理，即求取到s的最短路径；距离d为所求取的路径长，开始被赋值无穷大，pv表示路径，通过追溯pv可以显示实际的路径长。

算法的伪代码如下

void Graph::unweighted(Vextex s){    for each Vertex v    {        v.dist=INFINITY;        v.known=false;    }    s.dist=0;    for(int currDist=0;currDist

上述代码运算复杂度是O(V^2)

下面给出使用O(V+E）复杂度的算法，类似于拓扑排序，使用连接表可以降低算法的时间复杂度为O(V+E)。

void Graph::unweighted(Vertex s){    Queue
   
     q;    for each Vertex v        v.dist=INFINITY'    s.dist=0;    q.enqueue(s);    while(!q.isEmpty())    {        Vertex v=q.dequeue();        for each Vertex w adjacent to v            if(w.dist==INFINITY)            {                w.dist=v.dist+1;                w.path=v;                q.enqueue(w);            }    }}
   

上述算法的运行情况如下：

实际例子

代码参考：