数据结构笔记——图的广度优先遍历（BFS）

- 日理万妓 2023-02-17 14:54 31阅读 0赞

**目录**

一、树的广度优先遍历

二、图的广度优先遍历

三、树VS图

四、代码实现

五、广度优先遍历序列

六、遍历序列的可变性

七、算法存在的问题

八、BFS算法（Final版）

九、复杂度分析

十、广度优先生成树

十一、广度优先生成森林

十二、总结

## **一、树的广度优先遍历** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

通过根节点，可以找到下一层的结点2,3,4通过234又可以找到再下一层的结点5678

![20200614185456253.png][]

## **二、图的广度优先遍历** ##

![20200614185615771.png][]

![20200614185629584.png][]

![2020061418563533.png][]

广度优先序列：21453748

## **三、树VS图** ##

**树**

不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点

**图**

搜索相邻的顶点时，有可能搜到已经访问过的顶点

**树的广度优先遍历（层次遍历）**

①若树非空，则根节点入队

②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③重复②直到队列为空

## **四、代码实现** ##

**BFS要点**

**1.找到与一个顶点相邻的所有顶点**

**2.标记哪些顶点被访问过**

**3.需要一个辅助队列**

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
    }

![2020061419091688.png][]![20200614190930500.png][]

![20200614191125877.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

## **五、广度优先遍历序列** ##

![2020061419130168.png][]

从顶点1出发得到的广度优先遍历序列：12563748

从顶点2出发得到的广度优先遍历序列：21653748

从顶点3出发得到的广度优先遍历序列：34678215

## **六、遍历序列的可变性** ##

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一

同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一

## **七、算法存在的问题** ##

如果是非连通图，则无法遍历完所有结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]![20200614191634206.png][]

## **八、BFS算法（Final版）** ##

bool visited[MAX_VERTEX_NUM];    //访问标记数组
    
    void BSFTraverse(Graph G){    //对图G进行广度优先遍历
        for(i = 0; i < G.vexnum;++1)
            visited[i] = FALSE;        //访问标记数组初始化
        InitQueue(Q);        //初始化辅助队列Q
        for(i = 0; i < G.vexnum;++1)        //从0号顶点开始遍历
            if(!visited[i])        //对每个连通分量调用一次BFS
                BFS(G,i);        //vi未访问过，从vi开始BFS
    }
    
    
    
    //广度优先遍历
    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
    }

**结论：对于无向图，调用BFS函数的次数 = 连通分量数**

## **九、复杂度分析** ##

**空间复杂度**：最坏情况，辅助队列大小为O（|V|）

![20200614192147492.png][]

**时间复杂度**

邻接矩阵存储的图

访问|V|个顶点需要O（|V|）的时间

查找每个顶点的邻接点都需要O（|V|）的时间，而总共有|V|个顶点

时间复杂度 = O（|V|^2）

邻接表存储的图

访问|V|个顶点需要O（|V|）的时间

查找各个顶点的邻接点共需要O（|E|）的时间

时间复杂度 = O（|V| + |E|）

## **十、广度优先生成树** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

**邻接矩阵和邻接表存储**

![20200614192547270.png][]

![20200614192551786.png][]

![20200614192557410.png][]

![20200614192617874.png][]

**另一种邻接表存储**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5][]

![20200614192737991.png][]

![20200614192750952.png][]

![20200614192822994.png][]

![2020061419283757.png][]

**总结**

广度优先生成树由广度优先遍历过程确定、由于邻接表的表示方式不唯一，因此基于邻接表的广度生成树也不唯一

## **十一、广度优先生成森林** ##

**对于非连通图的广度优先遍历、可得到广度优先生成森林**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6][]

## **十二、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 7][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020061418540583.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200614185456253.png]: https://img-blog.csdnimg.cn/20200614185456253.png
[20200614185615771.png]: https://img-blog.csdnimg.cn/20200614185615771.png
[20200614185629584.png]: https://img-blog.csdnimg.cn/20200614185629584.png
[2020061418563533.png]: https://img-blog.csdnimg.cn/2020061418563533.png
[2020061419091688.png]: https://img-blog.csdnimg.cn/2020061419091688.png
[20200614190930500.png]: https://img-blog.csdnimg.cn/20200614190930500.png
[20200614191125877.png]: https://img-blog.csdnimg.cn/20200614191125877.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200614191137509.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200614191224352.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[2020061419130168.png]: https://img-blog.csdnimg.cn/2020061419130168.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200614191629384.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200614191634206.png]: https://img-blog.csdnimg.cn/20200614191634206.png
[20200614192147492.png]: https://img-blog.csdnimg.cn/20200614192147492.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200614192541559.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200614192547270.png]: https://img-blog.csdnimg.cn/20200614192547270.png
[20200614192551786.png]: https://img-blog.csdnimg.cn/20200614192551786.png
[20200614192557410.png]: https://img-blog.csdnimg.cn/20200614192557410.png
[20200614192617874.png]: https://img-blog.csdnimg.cn/20200614192617874.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200614192712288.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200614192737991.png]: https://img-blog.csdnimg.cn/20200614192737991.png
[20200614192750952.png]: https://img-blog.csdnimg.cn/20200614192750952.png
[20200614192822994.png]: https://img-blog.csdnimg.cn/20200614192822994.png
[2020061419283757.png]: https://img-blog.csdnimg.cn/2020061419283757.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200614193058195.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200614193207440.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70