数据结构–BFS求最短路

BFS求⽆权图的单源最短路径

注：⽆权图可以视为⼀种特殊的带权图，只是每条边的权值都为1

$以2为begin位置$

代码实现

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u)
{//d[i]表示从u到i结点的最短路径for(i = 0; i < G.vexnum; ++i){d[i] = inf;  //初始化路径长度path[i] = -1; //最短路径从哪个顶点过来}d[u] = 0;visited[u] = TRUE;EnQueue(Q, u);while(!isEmpty(Q))//BFS算法主过程{DeQueue(Q, u); //队头元素u出队for(w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)){if(!visited[w])//w为u的尚未访问的邻接顶点{d[w] = d[u] + 1; //路径长度加1path[w] = u; //最短路径应从u到Wvisited[w] = TRUE; //设已访问标记EnQueue(Q, w); //顶点w入队}}}
}

上图最终 d[]、 path[]、 visited[] 的情况

将其生成⼴度优先⽣成树

就是对BFS的⼩修改，在visit⼀个顶点时，修改
其最短路径⻓度 d[ ] 并在 path[ ] 记录前驱结点

2到8的最短路径⻓度 = d[8] = 3
通过path数组可知，2到8的最短路径为：$2\to 6\to 7\to 8$