一,广度优先搜索的思想
广度优先搜索(Breadth First Search,以下简称BFS)的思想是对一幅图G,从某个源结点s开始,依次访问其邻结点v1,v2...,访问完后,从被访问过的结点(v1)开始继续访问其邻结点v1.1、v1.2...,直到所有结点被访问完毕,简单来说就是对图一层一层的进行访问,访问完同一层级的结点后再访问后续结点。
访问完所有结点后,我们可以知道从源结点s开始能到达哪些结点以及经过的路径长度,以此生成一个“广度优先搜索树”,s作为其根结点,其余为s可以到达的结点v,s到v的距离为图G中s到v的最短路径长度。
二,BFS算法介绍
准备阶段:我们有个图G=(V,E),确定了一个源结点s,为了记录图的搜索情况,我们引进三个颜色:白色——代表未被访问的结点,灰色——已被访问的结点,但他的后续结点未被访问完,黑色——自己和其后续结点都已被访问的结点,初始状态下,所有结点都是白色,即都未被访问过。
算法过程:我们从源结点s开始,寻找s的邻结点,并将这n个邻结点标为灰色,表示已经被访问过,将源结点s标为黑色,表示他的邻结点都已经被访问过了,然后从这n个邻结点开始按顺序依次访问其邻结点,重复上述操作,直到所有结点都标为了黑色,搜索完成。我们在搜索的过程中同时需要构建一棵“广度优先搜索树”,一开始这棵树只有源结点s,然后每访问到一个白色结点,就将其加入该树,放在其父结点后,由于每个结点只能被访问一次,所以一个结点最多只有一个父结点。
三,BFS伪代码
BFS(G,s)
1. for each vertex u∈G.V-{s}
2. u.color=WHITE
3. u.d=∞
4. u.π=NULL
5. s.color=GRAY
6. s.d=0
7. s.π=NULL
8. Q=∅
9. ENQUEUE(Q,s)
10. while Q≠∅
11. u=DEQUEUE(Q)
12. for each v∈G.Adj[u]
13. if v.color==WHITE
14. v.color=GRAY
15. v.d=u.d+1
16. v.π=u
17. ENQUEUE(Q,v)
18. u.color=BLACK
在1-4行,对所有除了源结点s的结点进行初始化,将它们的颜色标为白色,s到它们的距离d设为无穷大,它们的前驱结点设为空;在5-7行,对源结点s进行初始化,颜色设为灰色,到源结点的距离d设为0,前驱结点设为空;在8-9行,定义了一个先进先出的队列Q,并设置为空,这个队列用于存放依次被访问到的结点(后续会将其弹出,因此这个队列存放的是当前还没被访问完的结点),因此我们先将源结点s放进去;在10-18行,进行的是结点的访问工作,当队列不为空时,即有结点没被访问完,我们定义一个结点变量u,从队列中弹出该未被访问的结点并存放到u中,然后遍历u的邻结点v,如果是白色的那么就设为灰色,并且让其到源结点的距离d=u到源结点的距离+u到v的距离(如果每条边没有被赋值,则默认+1),然后让v的前驱结点设为u,随后将v入队,这样一来队列中就存放这u的所有邻结点v,这些v都没被访问完,最后把u的颜色设为黑色表示他已经被访问完了。
以书上的例子为例,图a中,我们将源结点设为s,并将所有结点进行初始化,队列中有s;图b中我们弹出队列钟的首元素,即s,搜索s的邻结点,r、w并标为灰色,距离为1,并将w和r加入队列中,发现s的邻结点都被找到了,将s标为黑色;图c中弹出队列中的首元素w,寻找w的邻结点,有s、t、x,其中t和x是白色的,即没被搜索到的,将t和x入队列......直到最后,队列为空,所有元素都被遍历到了。
四,BFS的复杂度
1.空间复杂度
由于每个结点和每条边都要被存储,所以空间复杂度为O(V+E)
2.时间复杂度
对结点初始化的复杂度为O(V),在访问结点时,需要遍历每一条边,因此搜索时的复杂度为O(E),因此总时间复杂度为O(V+E)
五,BFS的代码
代码中圆形表示白色,三角形表示灰色,正方形表示黑色,其他结点在构造时已经初始化完毕所以没有写上去
void BFS(Graph * graph, Node * startNode)
{Node *u;startNode->setShape(TRIANGLE);startNode->setDistance(0);startNode->setPrevNode(NULL);queue<Node *> q;q.push(startNode);while (!q.empty()) {u = q.front();q.pop();vector<Node *> adj = u->getAdjNodeList();for (int i = 0; i < adj.size(); i++) {if (adj[i]->getShape() == CIRCLE) {adj[i]->setShape(TRIANGLE);adj[i]->setDistance(u->getDistance() + 1);adj[i]->setPrevNode(u);q.push(adj[i]);}}u->setShape(SQUARE);}
}
更多推荐
广度,导论,算法
发布评论