Breadth First Search
Reference:
BFS是把本身(點)能到的點先走過一次,走完後再去走過的點做重複的事
以下面例子為例:
- 從0開始,0會先探訪1跟2,
- 再去探訪1能走到的3,
- 2所能接觸到的點都被探訪過,所從3開始去做探訪,探訪到4之後結束
例子有利用到queue的特性
Example_1: 遍歷所有的點
0
/ \
1 2
\ /
3
|
4
#include<iostream>
#include <queue> // std::queue
#define graph_Max 5
bool visited[graph_Max] = {false};
static bool graph[graph_Max][graph_Max] = {
{0,1,1,0,0},
{1,0,0,1,0},
{1,0,0,1,0},
{0,1,1,0,1},
{0,0,0,1,0}};
void BFS(int);
std::queue<int> myqueue;
int main(int argc, char* argv[])
{
visited[0] = true;
BFS(0);
return 0;
}
void BFS(int v){
printf("%d\n",v);
for(int i = 0; i < graph_Max; i++)
if(graph[v][i] && !visited[i]) {
visited[i] = true;
myqueue.push(i);
}
while(!myqueue.empty()) {
int next = myqueue.front();
myqueue.pop();
BFS(next);
}
}
output:
0
1
2
3
4