Breadth First Search

Reference:

1. 魔人日誌: [練習] graph走訪程式

BFS是把本身(點)能到的點先走過一次,走完後再去走過的點做重複的事

以下面例子為例:

1. 從0開始,0會先探訪1跟2,
2. 再去探訪1能走到的3,
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