BFS与最短路径

BFS

基本步骤

要实现图的广度优先遍历，需要借助队列这一结构。

1. 将入口顶点入队，同时标记为已访问
2. 若队列不为空，则从队列中取出一个顶点访问
3. 检查与该顶点相连的其它顶点，若没有被访问过则入队，同时标记为已访问
4. 重复2、3步骤

示例代码

下面举一个例子：

#include<iostream>#include<vector>#include<queue>std::vector<std::vector<int>>g_Graph;staticvoidInput(){intvertexNums,edgeNums;std::cin>>vertexNums>>edgeNums;g_Graph.resize(vertexNums+1,std::vector<int>(vertexNums+1));intfrom,to,weight;for(size_t i=0;i<edgeNums;i++){std::cin>>from>>to>>weight;g_Graph[from][to]=weight;g_Graph[to][from]=weight;}}staticvoidBFS(){std::vector<bool>visited(g_Graph.size(),false);std::queue<int>queue;queue.push(1);visited[1]=true;intvertex;while(!queue.empty()){vertex=queue.front();queue.pop();std::cout<<vertex<<' ';for(size_t i=1;i<g_Graph.size();i++){if(!visited[i]&&g_Graph[vertex][i]!=0){queue.push(i);visited[i]=true;}}}std::cout<<std::endl;}intmain(){Input();BFS();return0;}

读者可以用这个代码自行测试。

BFS与无权图最短路径查找

BFS可以用于查找无权图的最短路径。BFS是层层递进进行遍历的，第一次访问某一个顶点的时候，此时经过的路径就是从起始顶点到该顶点的最短路径。

下面是示例代码：

staticstd::vector<std::vector<int>>g_Graph;staticvoidBFSGetShortestPath(intstart,inttarget){std::vector<bool>visited(g_Graph.size(),false);std::queue<int>queue;std::vector<int>parent(g_Graph.size(),-1);// 用于回溯路径，下标为顶点，元素为其上一个顶点queue.push(start);visited[start]=true;intvertex;while(!queue.empty()){vertex=queue.front();queue.pop();if(vertex==target)// 如果当前访问的顶点是目标顶点{std::vector<int>path;intcursor=target;while(cursor!=-1)// 通过parent获得路径{path.push_back(cursor);cursor=parent[cursor];}std::reverse(path.begin(),path.end());// 反转之后得到正确的路径for(auto&a:path)std::cout<<a<<' ';std::cout<<std::endl;return;}for(size_t i=1;i<g_Graph.size();i++)// 正常的BFS遍历操作{if(visited[i]==false&&g_Graph[vertex][i]!=0)// 遍历vertex的邻接顶点{queue.push(i);visited[i]=true;parent[i]=vertex;}}}}