注意:本内容主要是介绍用BFS实现图的遍历,所以需要对图的结构有所了解。
一、什么是BFS?
BFS(Breadth First Search,广度优先搜索,又名宽度优先搜索),与深度优先算法DFS往一个方向“死磕到底,不撞南墙不回头”的思维方式不同,广度优先搜索算法关注的重点在于对每一层结点进行下一层的访问。
二、BFS算法介绍
BFS算法和核心思路就是:从某个点一直把其邻接点走完,然后任选一个邻接点把与之邻接的未被遍历的点走完,如此反复走完所有结点。类似于树的层序遍历。
所以,BFS的核心就是要把当前在哪作为一个状态存储,并将这个状态交给队列进行入队操作
算法步骤(用队列实现)
a) 访问指定起始点。
b) 访问当前顶点的邻接顶点有未被访问的顶点,并将之放入队列中。
c) 删除队列的队首节点。访问当前队列的队首,前面的步骤。直到队列为空。
d) 若途中还有顶点未被访问,则再选一个点作为起始顶点。重复前面的步骤(针对非连通图)。
三.、案例图示
我们直接上案例进行说明,就本图而言,其访问顺序可以是:1--2--3--4--5(并不唯一)
遍历图的具体步骤如下:
首先从1开始,1结点处连接着2,3两个结点,所以我们先访问2,3两个结点。同时我们把两个结点按照访问顺序入队,比如,选择2,3为入队顺序,所以之后我们先出队状态2,再来依次访问结点2所连接的4,5两个结点,同样的,按照顺序入队4,5结点,然后操作完状态2之后,我们再出队状态3,并依次访问它的后续,但此时发现3的后续结点已经访问过了,并且检查发现所有的结点都已经被访问完毕,说明遍历结束了。最后我们得到图的遍历次序:1--2--3--4--5
四、相关代码
具体实现遍历图的代码示例:
void BFSL(int pos,pGraph G,int visited[30])//从pos点开始进行广度优先遍历无向图
{
int queue[G->Vnum];//队列辅助BFS遍历
int head=0,tail=0;//队头、队尾指针
Arcnode* p;
queue[tail]=pos;
visited[pos]=1;//标记遍历过
tail++;
while(head!=tail)
{
pos=queue[head];//出队操作
head++;
printf("%d ",pos);
p=G->vertice[pos].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)//判断是否遍历过
{
queue[tail]=p->adjvex;//入队操作
visited[p->adjvex]=1;//标记遍历过
tail++;
}
p=p->next;
}
}
}
我们使用BFS解决问题的一般模板如下:
/**
* 返回合适的检索数据
*/
int BFS(Node root, Node target)
{
Queue<Node> queue; //创建队列
int step = 0; // 当前队列的步骤点
// initialize
add root to queue;
// BFS
while (queue is not empty)
{
step = step + 1;
//步数逐渐增加
int size = queue.size();
for (int i = 0; i < size; ++i)
{
Node cur = the first node in queue;
if cur is target
return step - 1;
for (Node next : the neighbors of cur)
{//这里常用一个二维方向数组实现
add next to queue;
}
remove the first node from queue;
}
}
return -1; //出错返回值
}
五、BFS的一些应用场景
BFS算法的实际应用场景:文章来源:https://www.toymoban.com/news/detail-405537.html
最典型的有地图搜索,迷宫寻路等这些需要有“状态”以及状态改变场景的搜索算法,同时BFS由于不需要像DFS算法那样回溯,所以效率可能会比DFS更高一些。文章来源地址https://www.toymoban.com/news/detail-405537.html
到了这里,关于广度优先搜索(BFS)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!