数据结构笔记——最短路径BFS算法

今天药忘吃喽~ 2023-02-18 08:21 235阅读 0赞

> 写在前面：科班出身，应届考研党，愿21考研成功上岸，冲冲冲！

**目录**

一、最短路径问题

二、BFS求无权图的单源最短路径

三、代码实现

四、总结

## **一、最短路径问题** ##

单源最短路径——BFS算法、Dijkstra算法

其中BFS算法（无权图）、Dijkstra算法（带权图，无权图）

各顶点间的最短路径——Floyd算法（带权图、无权图）

## **二、BFS求无权图的单源最短路径** ##

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

![20200616184340241.png][]

![20200616184347970.png][]

![20200616184353259.png][]

![20200616184412397.png][]

![2020061618441818.png][]

![20200616184423521.png][]

![20200616184428559.png][]

![20200616184433241.png][]

## **三、代码实现** ##

bool visited[MAX_VERTEX_NUM];//访问标记数组
    
    //广度优先遍历
    void BFS(Graph G,int v){        //从顶点v出发，广度优先遍历图G
        visit(v);            //访问初始顶点v
        visited[v] = TRUE;        //对v做已访问标记
        Enqueue(Q,v);        //顶点v入队列Q
        while(!isEmpty(Q)){
            DeQueue(Q,v);        //顶点v出队列
            for( w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
                //检测v所有邻接点
                if(!visited[w]){        //w为v的尚未访问的邻接顶点
                    visit(w);            //访问顶点w
                    visited[w] = TRUE;        //对w做已访问标记
                    EnQueue(Q,w);        //顶点w入队列
            }//if
        }//while
    }

//求顶点u到其他顶点的最短路径
    void BFS_Distance(Graph G,int u){
        for(i = 0;i < G.vexnum;++i){
            d[i] = w;
            path[i] = -1;
        }
        d[u] = 0;
        visited[u] = TRUE;
        EnQueue(Q,u);
        while(!isEmpty(Q)){
            DeQueue(Q,u);
            for(w = FirstNeighbor(G,u);w >= 0;w = NextNeighbor(G,u,w))
                if(!visited[w]){
                    d[w] = d[u] + 1;
                    path[w] = u;
                    visited[w] = TRUE;
                    EnQueue(Q,w);
            }//if
        }//while
    }

![20200616185229776.png][]![20200616185234201.png][]![20200616185240180.png][]

![20200616185250545.png][]![20200616185254526.png][]![20200616185258894.png][]

![20200616185309403.png][]![20200616185254526.png][]![20200616185258894.png][]

![20200616185319801.png][]![20200616185323942.png][]![20200616185329194.png][]

![20200616185413886.png][]![20200616185323942.png][]![20200616185329194.png][]

![20200616185434468.png][]![20200616185438923.png][]![20200616185445186.png][]

![20200616185454354.png][]![20200616185459682.png][]![20200616185503536.png][]

![20200616185527269.png][]![2020061618553533.png][]![20200616185539470.png][]

![20200616185546556.png][]![20200616185552807.png][]![2020061618555941.png][]

![2020061618561810.png][]![202006161856261.png][]![20200616185630985.png][]

![20200616185837499.png][]![20200616185841581.png][]![20200616185846238.png][]

![20200616185851318.png][]![20200616185855144.png][]![20200616185846238.png][]

![20200616185902324.png][]![20200616185906561.png][]![20200616185911812.png][]

![20200616185916778.png][]![20200616185922690.png][]![20200616185926788.png][]

![20200616185933912.png][]![20200616185937874.png][]![20200616185941436.png][]

![20200616185946354.png][]![2020061618595177.png][]![20200616185954586.png][]

![20200616185959199.png][]![20200616190004430.png][]![20200616190008459.png][]

![20200616190014577.png][]![20200616190017555.png][]![20200616190021660.png][]

![20200616190027160.png][]![20200616190017555.png][]![20200616190021660.png][]

## **四、总结** ##

![20200616185229776.png][]

对应的广度优先生成树为

![20200616190134387.png][]

思路就是对BFS的小修改，在visit一个顶点时，修改其最短路径长度d\[\]并在path\[\]记录前驱结点

2到8的最短路径长度=d\[8\]=3

通过path数组可知，2到8的最短路径为：8<- 7 <- 6 <- 2

[20200616184340241.png]: https://img-blog.csdnimg.cn/20200616184340241.png
[20200616184347970.png]: https://img-blog.csdnimg.cn/20200616184347970.png
[20200616184353259.png]: https://img-blog.csdnimg.cn/20200616184353259.png
[20200616184412397.png]: https://img-blog.csdnimg.cn/20200616184412397.png
[2020061618441818.png]: https://img-blog.csdnimg.cn/2020061618441818.png
[20200616184423521.png]: https://img-blog.csdnimg.cn/20200616184423521.png
[20200616184428559.png]: https://img-blog.csdnimg.cn/20200616184428559.png
[20200616184433241.png]: https://img-blog.csdnimg.cn/20200616184433241.png
[20200616185229776.png]: https://img-blog.csdnimg.cn/20200616185229776.png
[20200616185234201.png]: https://img-blog.csdnimg.cn/20200616185234201.png
[20200616185240180.png]: https://img-blog.csdnimg.cn/20200616185240180.png
[20200616185250545.png]: https://img-blog.csdnimg.cn/20200616185250545.png
[20200616185254526.png]: https://img-blog.csdnimg.cn/20200616185254526.png
[20200616185258894.png]: https://img-blog.csdnimg.cn/20200616185258894.png
[20200616185309403.png]: https://img-blog.csdnimg.cn/20200616185309403.png
[20200616185319801.png]: https://img-blog.csdnimg.cn/20200616185319801.png
[20200616185323942.png]: https://img-blog.csdnimg.cn/20200616185323942.png
[20200616185329194.png]: https://img-blog.csdnimg.cn/20200616185329194.png
[20200616185413886.png]: https://img-blog.csdnimg.cn/20200616185413886.png
[20200616185434468.png]: https://img-blog.csdnimg.cn/20200616185434468.png
[20200616185438923.png]: https://img-blog.csdnimg.cn/20200616185438923.png
[20200616185445186.png]: https://img-blog.csdnimg.cn/20200616185445186.png
[20200616185454354.png]: https://img-blog.csdnimg.cn/20200616185454354.png
[20200616185459682.png]: https://img-blog.csdnimg.cn/20200616185459682.png
[20200616185503536.png]: https://img-blog.csdnimg.cn/20200616185503536.png
[20200616185527269.png]: https://img-blog.csdnimg.cn/20200616185527269.png
[2020061618553533.png]: https://img-blog.csdnimg.cn/2020061618553533.png
[20200616185539470.png]: https://img-blog.csdnimg.cn/20200616185539470.png
[20200616185546556.png]: https://img-blog.csdnimg.cn/20200616185546556.png
[20200616185552807.png]: https://img-blog.csdnimg.cn/20200616185552807.png
[2020061618555941.png]: https://img-blog.csdnimg.cn/2020061618555941.png
[2020061618561810.png]: https://img-blog.csdnimg.cn/2020061618561810.png
[202006161856261.png]: https://img-blog.csdnimg.cn/202006161856261.png
[20200616185630985.png]: https://img-blog.csdnimg.cn/20200616185630985.png
[20200616185837499.png]: https://img-blog.csdnimg.cn/20200616185837499.png
[20200616185841581.png]: https://img-blog.csdnimg.cn/20200616185841581.png
[20200616185846238.png]: https://img-blog.csdnimg.cn/20200616185846238.png
[20200616185851318.png]: https://img-blog.csdnimg.cn/20200616185851318.png
[20200616185855144.png]: https://img-blog.csdnimg.cn/20200616185855144.png
[20200616185902324.png]: https://img-blog.csdnimg.cn/20200616185902324.png
[20200616185906561.png]: https://img-blog.csdnimg.cn/20200616185906561.png
[20200616185911812.png]: https://img-blog.csdnimg.cn/20200616185911812.png
[20200616185916778.png]: https://img-blog.csdnimg.cn/20200616185916778.png
[20200616185922690.png]: https://img-blog.csdnimg.cn/20200616185922690.png
[20200616185926788.png]: https://img-blog.csdnimg.cn/20200616185926788.png
[20200616185933912.png]: https://img-blog.csdnimg.cn/20200616185933912.png
[20200616185937874.png]: https://img-blog.csdnimg.cn/20200616185937874.png
[20200616185941436.png]: https://img-blog.csdnimg.cn/20200616185941436.png
[20200616185946354.png]: https://img-blog.csdnimg.cn/20200616185946354.png
[2020061618595177.png]: https://img-blog.csdnimg.cn/2020061618595177.png
[20200616185954586.png]: https://img-blog.csdnimg.cn/20200616185954586.png
[20200616185959199.png]: https://img-blog.csdnimg.cn/20200616185959199.png
[20200616190004430.png]: https://img-blog.csdnimg.cn/20200616190004430.png
[20200616190008459.png]: https://img-blog.csdnimg.cn/20200616190008459.png
[20200616190014577.png]: https://img-blog.csdnimg.cn/20200616190014577.png
[20200616190017555.png]: https://img-blog.csdnimg.cn/20200616190017555.png
[20200616190021660.png]: https://img-blog.csdnimg.cn/20200616190021660.png
[20200616190027160.png]: https://img-blog.csdnimg.cn/20200616190027160.png
[20200616190134387.png]: https://img-blog.csdnimg.cn/20200616190134387.png