从零开始学数据结构系列之第四章《广度优先遍历BFS》

文章目录

广度优先遍历（BFS）
概念
广度优先遍历算法步骤
总代码
往期回顾

广度优先遍历（BFS）

概念

广度优先遍历(Breadth First Search)，又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

简单来说就类似于我们之前学的层次遍历

广度优先遍历算法步骤

访问初始结点 v 并标记结点 v 为已访问
结点 v 入队列
当队列非空时，继续执行，否则算法结束
出队列，取得头结点 u
查找结点 u 的第一个邻接结点 w
若结点 u 的邻接结点 w 不存在，则转到步骤 3；否则循环执行以下三个步骤
1. 若结点 w 尚未被访问，则访问结点 w 并标记为已访问
2. 结点 w 入队列
3. 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w，转到步骤6

我们用的是以下这张图：

在这里插入图片描述

总代码

/*
*	总体思路感觉与DFS差不多
*	基本就是层次遍历的思想 + DFS写法内容
*/
void BFS(Graph* G, int* visited, int index) 
{
	int j = 0;
	int i = 0;
    Queue* Q = initQueue();
    printf("%c ", G -> vexs[index]);
    visited[index] = 1;
    enQueue(Q, index);
    while (!isEmpty(Q)) 
	{
        i = deQueue(Q);
        for (j = 0; j < G -> vexNum; j++) 
		{
            if (G -> arcs[i][j] && !visited[j]) 
			{
                printf("%c ", G -> vexs[j]);
                visited[j] = 1;
                enQueue(Q, j);
            }
        }
    }
}

遍历过程如下：

<1>先输出顶点A,此时flag[0]=1,表示第一列（j=0）已经有顶点A输出，这里保证每个顶点都输出的话，就要做这个标记，之后就不会再来这一列（j=0）找顶点了

i\j	→(j)	0	1	2	3	4
↓(i)	<1>	A	B	C	D	E
0	A	0 flag[0]=1	1	1	1	0
1	B	1	0	1	1	1
2	C	1	1	0	0	0
3	D	1	1	0	0	1
4	E	0	1	0	1	0

<2>输出顶点A后，继续在A行里面找1，B，C，D都有1，所以顶点都输出，并将其顶点对应的下标j值存入队列中，之后会访问这些j下标的行。另外还flag[1]=flag[2]=flag[3]=1，标志着BCD列都没有顶点输出了。

i\j	→(j)	0	1	2	3	4
↓(i)	<2>	A	B	C	D	E
0	A	0 flag[0]=1	1flag[1]=1	1flag[2]=1	1flag[3]=1	0
1	B	1	0	1	1	1
2	C	1	1	0	0	0
3	D	1	1	0	0	1
4	E	0	1	0	1	0

**<3>**之后出队的是1，i=1，就来到了B行，B中ABCD列顶点都标记输出过了，E列有1，未标记，表示有边，输出E，之后j=4这个下标入队。到C行之后每一行就没有顶点了输出，因为列全标记了，遍历才结束。

i\j	→(j)	0	1	2	3	4
↓(i)	<3>	A	B	C	D	E
0	A	0 flag[0]=1	1flag[1]=1	1flag[2]=1	1flag[3]=1	0
1	B	1	0	1	1	1flag[4]=1
2	C	1	1	0	0	0
3	D	1	1	0	0	1
4	E	0	1	0	1	0

总结：

flag是用来标记列的，可以这样认为：一列代表一个顶点，要是全部的列标记了就可以证明遍历结束了。另外，行只是用来看是否有到达下一个顶点的条件（有1就有边），这里行的执行顺序是按入队出队顺序决定的。

往期回顾

标签：结点,遍历,第三章,BFS,flag,从零开始,二叉树,顶点
From： https://blog.csdn.net/qq_62548908/article/details/140189360

从零开始学数据结构系列之第四章《广度优先遍历BFS》

文章目录

广度优先遍历（BFS）

概念

广度优先遍历算法步骤

总代码

往期回顾

相关文章

赞助商

阅读排行

从零开始学数据结构系列之第四章《 广度优先遍历BFS》

文章目录

广度优先遍历（BFS）

概念

广度优先遍历算法步骤

总代码

往期回顾

相关文章

赞助商

阅读排行

从零开始学数据结构系列之第四章《广度优先遍历BFS》