算法系列之图--BFS
广度优先搜索以源结点s为出发点,算法始终将已发现和未发现结点之间的边界,沿其广度方向向外扩展。也即算法需要在发现所有距离源结点s为k的所有结点之后才会去发现距离源结点距离为k+1的其他结点。
talk is cheap,show me the code!上具体的代码,最容易解释这一切。
该例子是以无向图为基础,代码中注释有具体说明,不在解释每一步:
1 #include <iostream> 2 #include <list> 3 #include <queue> 4 using namespace std; 5 6 //无向图 7 class Graph{ 8 private: 9 int v;//图的节点数 10 list<int> *adj;//指向包含临接链表的数组 11 public: 12 Graph(int v); 13 void addEdge(int start,int end);//添加临接边 14 void BFS(int s);//广度优先搜索 15 }; 16 17 Graph::Graph(int v){ 18 this->v = v; 19 adj = new list<int>[v]; 20 } 21 22 //无向图中添加一条边在临接表中添加两项 23 void Graph::addEdge(int start,int end){ 24 adj[start].push_back(end); 25 adj[end].push_back(start); 26 } 27 28 void Graph::BFS(int s){ 29 //先标记所有结点都未被访问 30 bool* visited = new bool[v]; 31 for (int i=0;i<v;i++) 32 visited[i] = false; 33 //创建队列 34 queue<int> q = queue<int>(); 35 //先设置源结点 36 visited[s] = true; 37 q.push(s); 38 39 while(!q.empty()){ 40 int node = q.front(); 41 cout<<node<<" "; 42 q.pop(); 43 //node结点的临接表 44 list<int> nlist = adj[node]; 45 list<int>::iterator beg = nlist.begin(); 46 for (;beg != nlist.end();beg++){ 47 if (!visited[*beg]){ 48 visited[*beg] = true; 49 q.push(*beg); 50 } 51 } 52 } 53 cout<<"\n"; 54 } 55 56 int main(){ 57 Graph g = Graph(6); 58 g.addEdge(0,1); 59 g.addEdge(0,2); 60 g.addEdge(0,5); 61 g.addEdge(1,3); 62 g.addEdge(2,3); 63 g.addEdge(2,5); 64 g.addEdge(2,4); 65 g.addEdge(4,5); 66 g.BFS(0); 67 68 return 0; 69 }
该例子中每个结点就是用一个整数表示,更复杂点的话,每个结点可以组织成一个node结构体,可以给每个node结点添加距离属性等。
运行结果如下 示:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。