너비우선탐색(BFS ; Breadth First Search)

 

깊이우선탐색(DFS)와 달리 인접한 정점(V)를 모두 방문하며, 탐색을 진행한다.

우선 자료구조로 큐를 사용한다.

큐는 FIFO(First in First out)으로 가장 처음에 넣은 것이 큐에서 가장 처음으로 빠질 수 있다.

 

그래프 G(V,E)가 아래와 같이 구성되어 있을 때 시작 정점을 5번 정점이라고 하자.

그러면 5번정점을 시작으로 탐색을 하게 되면,

이때 5번정점을 큐에 넣으며, 방문처리한다.

탐색을 시작하며 5번정점을 꺼내 인접 정점을 탐색한다.

 

그리고 5번 정점에서 인접하며, 방문하지 않은 정점을 모두 큐에 넣는다.

인접한 정점의 정보는 오름차순으로 정렬되어 있다고 하자.

그렇게 되면 방문표시를 하며 정점 4, 6, 8 순서로 큐에 들어가게 된다.

 

 

 

이후 4번정점을 가장 먼저 넣었으므로

4번 정점을 꺼내고 인접한 정점을 찾는다.

인접한 1번 정점을 큐에 넣으며, 방문처리 한다.

큐에는 6 , 8 , 1 순으로 정점이 저장되어있다.

이후 큐에서 6번 정점을 꺼내어 인접한 정점을 큐에 담는다.

3번, 9번 정점이 방문하지 않았은 정점이므로 큐에 담으며, 방문처리한다.

큐에는 8, 1, 3, 9 번 정점이 들어가 있다.

이후 8번 정점을 꺼내어 인접하며, 방문하지 않은 정점을 큐에 넣으며 방문처리한다.

그렇다면 7번 정점을 큐에 넣을 수 있다.

큐에는 1, 3, 9, 7 번 정점이 들어가 있다.

이후 모든 정점을 방문하였고, 큐에는 아직 정점이 남아있다.

그렇지만 큐에서 빼며 다른 정점을 탐색하려고 할 때

모든 정점이 방문되었으므로 더 이상 탐색을 진행하지 않지만,

 

큐가 비어있을 때 까지 탐색을 진행한다.

 

그렇다면 방문순서는

5번 -> 4번 -> 6번 -> 8번 -> 1번 -> 3번 -> 9번 -> 7번 순서가 된다.

 

위 내용을 코드로 작성하면

아래와 같을 수 있다.

결과는 동일하게 방문 순서대로 나온다.

 

#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef vector<int> VI;
VI edge[10];
bool vis_vertex[9];
 
void BFS(int start_node){
    queue<int> Q;
    Q.push(start_node);
    vis_vertex[start_node] = true;
    while(!Q.empty()){
        int here = Q.front();
        Q.pop();
        printf("visit vertex %d \n", here);
        for(auto iter = edge[here].begin() ; iter != edge[here].end() ; iter++){
            int there = *iter;
            if(!vis_vertex[there]){
                vis_vertex[there] = true;
                Q.push(there);
            }
        }
    }
    return ;
}
int main(){
    /*
        input data ; 간선 정보
        1 4
        4 5
        5 6
        5 8
        7 8
        6 9
        3 6
    */
    for(int i = 0 ; i < 7 ; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
        sort(edge[u].begin(), edge[u].end());
        sort(edge[v].begin(), edge[v].end());
    }
    BFS(5);
    
    return 0;
}
/*
Success    time: 0 memory: 16064 signal:0
visit vertex 5 
visit vertex 4 
visit vertex 6 
visit vertex 8 
visit vertex 1 
visit vertex 3 
visit vertex 9 
visit vertex 7 
*/

012345