图的广度优先搜索(BFS)与树的广度优先搜索类似。与树不同的是,图中可能存在循环。所我们可能会再次访问到同一个节点。为了表面多次处理同一个节点,我们要布尔变量数据记录节点有没有被访问过。为了简化,我们假设所有的节点都是从根节点可达的。
比如在下图中,我们从节点2出发。当我们访问到节点0时,我们寻找所有与他相邻的节点。节点2就是与0相邻的节点,如果我们不对已访问的节点做标记,那么节点2就会被重复访问。这样的话,算法将会一直进行下去。对下图进行广度优先搜索的结果是2,0,3,1.
以下C++程序是从给定节点进行广度优先搜索的一个简单实现。图的存储使用了邻接链表法。STL的list容器用来存储邻接节点以及与广度优先搜索需要的节点队列。
#include<list>
#include<iostream>
//Program to print BFS traversal from a given source vertex. BFS(int s)
//traverses vertices reachable from s
using namespace std;
//The class represents a directed graph using adjacency lists
class Graph {
int V; //No. of vertices
list<int> *adj;
public:
Graph(int V); //Constructor
~Graph();
void addEdge(int v, int w); //function to add an edge to graph
void BFS(int s); //print BFS traversal from a given source s
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
Graph::~Graph() {
delete []adj;
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::BFS(int s) {
//Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
}
//Create a queue for BFS
list<int> queue;
queue.push_back(s);
//"i" will be used to get all adjacent vertices of vertex
list<int>::iterator i;
while (!queue.empty()) {
//Dequeue a vertex from queue and print it
s = queue.front();
cout<<s<<" ";
queue.pop_front();
visited[s] = true;
//Get all adjacent vertices of the Dequeued vertex s
//If a adjacent has not been visited, then mark it visited
//and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); i++) {
if (!visited[*i]) {
queue.push_back(*i);
}
}
}
delete []visited;
}
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal (starting from vertex 2) \n";
g.BFS(2);
return 0;
}
参考资料
- http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
原文链接: https://www.cnblogs.com/vincently/p/4769422.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/221259
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!