그래프 탐색방법 - BFS

이전글을 이어 이번에는 BFS에 대해 설명하도록 하겠다. 

이전글은 DFS에 대한 설명이며 http://free-from-anxiety.tistory.com/8 를 통해 볼 수있다. 

○ BFS(너비 우선 탐색)

너비 우선 탐색이란 최대한 넓게 나가 그래프를 탐색하는 방법을 말한다.

  이것은 큐를 통해 구현을 하고 DFS보다 더 자주 쓰인다.

DFS보다 더 자주 쓰이는 이유가  모든 가중치가 1 이라면 최단거리를 탐색하는 방법을 찾는데 사용된다 라는 점이다.

이해가 쉽도록 그림을 이용해 설명하겠다.

i	1	2	3	4	5	6
Check[i]	1	0	0	0	0	0

현재 정점	1
순서	1
큐	1

i	1	2	3	4	5	6
Check[i]	1	1	0	0	1	0

현재 정점	1
순서	1 2 5
큐	1 2 5

더이상 정점 1에서 갈 곳이 없기에 큐의 앞의 값을 빼면서 정점을 이동한다.  큐의 맨 앞의 값이 정점이 된다.

현재 정점	2
순서	1 2 5
큐	2 5

i	1	2	3	4	5	6
Check[i]	1	1	1	0	1	0

현재 정점	2
순서	1 2 5 3
큐	2 5 3

현재 정점	5
순서	1 2 5 3
큐	5 3

i	1	2	3	4	5	6
Check[i]	1	1	1	1	1	0

현재 정점	5
순서	1 2 5 3 4
큐	5 3 4

현재 정점	3
순서	1 2 5 3 4
큐	3 4

현재 정점	4
순서	1 2 5 3 4
큐	4

i	1	2	3	4	5	6
Check[i]	1	1	1	1	1	1

현재 정점	4
순서	1 2 5 3 4 6
큐	4 6

현재 정점	6
순서	1 2 5 3 4 6
큐	6

현재 정점
순서	1 2 5 3 4 6
큐

큐가 비게 되면 DFS의 탐색이 끝난 것이다.

이를 코드를 통해 나타내면 다음과 같다.

bool check[1001];

vector<int>a[1001];

void bfs(int x){

queue<int> q;

//    시작점을 큐에 넣는데 체크값도 true로 넣어준다.

check[1] = true;

    q.push(1);

    while (!q.empty()) {

        int x = q.front();  //제일 앞에 있는 x 의 값을 빼 다음 정점을 구한다.

        q.pop();

        

        // 인접행렬

        for(int i=1;i<=n; i++){

            if(a[x][i] ==1 && check[i] ==false){

                check[i] = true;

                q.push(i);

            }

        }

        

        // 인접 리스트

        for (int i=0; i<a[x].size(); i++){

            int y = a[x][i];

            if(check[y] ==false){

                check[y] = true;

                q.push(y);

            }

        }

    }

다음 포스트에는 [1206] 백준 연습문제를 풀어보도록 하겠다.