BFS(Breadth-First-Search) 알고리즘

BFS(Breadth-First-Search) Algorithm

BFS Algorithm

- 그래프나 트리같은 자료구조에서 사용하는 Search 알고리즘

- DFS에서는 재귀 호출로 구현하는 경우가 많지만, BFS에서는 보통 queue 자료구조를 사용해 구현한다.

- 갈 수 있는 경로를 쭉 따라가는 DFS와 달리, 현재 Vertex에서 갈 수 있는 모든 정점을 방문한 후 방문한 정점을 기준으로 다시 갈 수 있는 모든 정점을 방문하는 식으로 진행된다.

BFS Complexity

- 인접 리스트를 이용해 그래프를 구현하는 경우와 인접 행렬을 이용해 구현하는 경우에 따라 시간복잡도가 다름

1) 인접 리스트

- 한 정점에서 방문할 수 있는 정점을 간선 기준으로 탐색할 수 있기 때문에 O(V+E)의 시간 복잡도를 가진다.

2) 인접 행렬

- 방문할 정점을 찾을 때 모든 정점을 탐색하며 현재 정점에서 갈 수 있는 정점을 찾기 때문에 O(V^2)의 시간 복잡도를 가진다.

V: 정점의 갯수, E: 간선의 갯수

BFS Process

- 방문하지 않은 정점(또는 선택한 한 정점)에서 시작한다.

- 현재 정점에서 갈 수 있는 정점을 모두 Queue에 넣는다.

- 방문할 정점이 이미 방문했던 정점이라면 Queue에 넣지 않는다.

Example) BFS 과정

- 양방향 그래프에서의 BFS

- 1번 노드에서 시작한다고 가정

먼저 방문 여부를 확인할 Visit배열을 모두 0(false)로 초기화하고, queue를 생성한다. 그 후에 1번 정점부터 탐색을 시작한다.

1번 정점을 방문하고 재 검색하지 않기 위해 Visit배열의 값을 1(true)로 바꿔준다. 그 후에 1번 정점에서 갈 수 있는 정점(2,3,5)들을 queue에 넣어준다.

queue의 front에 있는 정점을 탐색한다. 2번 정점으로 가서 Visit배열의 값을 1(true)로 바꿔준다. 그 후에 2번 정점에서 갈 수 있는 정점(7,6)들을 다시 queue에 넣는다.

queue에서 다시 front를 꺼내 탐색을 이어간다. 3번 정점으로 가서 Visit배열의 값을 1(true)로 바꿔준다. 그 후에 3번 정점에서 갈 수 있는 정점(4,6)을 넣어준다. 여기서는 2번 정점에서 6번을 넣었기 때문에 queue 넣지 않아도 된다. 이 것은 어떻게 구현하느냐에 따라 달라지는데 넣어주면서 Visit배열을 업데이트하는 경우 queue에 넣어주지 않아도 되고 이런 방식이 아니라면 queue에 중첩된 값이 들어가게 된다. Visit배열을 업데이트하기 때문에 이 방법에서는 queue에서 꺼내고 visit배열을 확인하는 두 가지 과정이 추가된다. 여기서는 중첩되는 값은 넣지 않게 했다.

이번에도 queue에 저장된 맨 앞의 정점을 꺼낸다. 이 5번 정점에서 갈 수 있는 정점은 4번이 있지만 이미 queue에 들어가있기 때문에 queue에 다시 넣지 않는다.

queue의 맨 앞 정점 6번을 꺼낸 후 탐색을 진행한다. 6번 정점에서 갈 수 있는 정점 2,4는 Visit배열을 확인하고 이미 방문했던 정점들이기 때문에 queue에 넣지 않고 6번 정점의 탐색을 끝난다.

7번 정점을 꺼낸 후 탐색을 한다. 7번 정점은 6번 정점과 마찬가지로 방문할 수 있는 정점이 2번이 있지만 이미 방문했던 정점이기 때문에 재 탐색을 하지 않고 7번 정점의 탐색은 끝난다.

queue에 남아있는 마지막 정점인 4번 정점을 꺼낸다. 4번 정점에서 갈 수 있는 정점인 3,5 정점도 역시 방문했던 정점이기 때문에 queue에 넣지 않고 4번 정점의 탐색도 끝난다.

queue에 남은 것이 없기 때문에 이렇게 해서 BFS방식으로의 탐색은 끝이난다. queue가 비어질 때, 즉 갈 수 있는 모든 정점을 탐색하게 되면 BFS는 종료된다.

모든 정점을 탐색하기 위해서는 1번 정점뿐만 아니라 방문하지 않은 다른 정점도 확인해야한다. 여기서는 1번 정점에서 모든 정점을 갈 수 있는 경우를 설명했다.

보통 BFS는 너비우선탐색으로 해당 정점에서 정점을 몇 번 거쳐서(깊이) 갈 수 있는 지 확인할 수 있는 탐색 방법이다. 그림에서는 Visit배열을 모두 1,0으로 설정했지만 1,0 대신 깊이를 저장하는 방법을 많이 쓴다.

BFS Algorithm Source Code

- 양방향 그래프에서의 BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int *visit;            // 방문했던 Vertex인지 확인하는 배열
int Vertex, Edge;    // Vertex수, Edge 수
vector <int> *course;    // vec[a] = b : a->b로 갈 수 있다는 것을 의미
int src_ver, dst_ver;    // edge를 입력받기 위한 변수
queue <pair<int,int>> que;        // depth에 따라 방문하기 위한 queue    (first = vertex_number, second = depth)
 
void BFS(int ver_num) {
    que.push(make_pair(ver_num,1));
    cout << "방문 순서 : ";
    while (!que.empty()) {
        int ver = que.front().first;
        int dep = que.front().second;
        if (!visit[ver]) {
            cout << ver << " ";
        }
        visit[ver] = dep;    // 1번 vertex부터의 깊이(1번을 깊이 1이라고 가정)
        que.pop();
        for (int i = 0; i < course[ver].size(); i++) {
            if (!visit[course[ver][i]]) {    // 현재 vertex에서 갈 수 있고 방문하지 않은 vertex 탐색
                que.push(make_pair(course[ver][i], dep + 1));
            }
        }
    }
    cout << endl;
    return;
}
 
int main()
{
    cin >> Vertex >> Edge;
    course = new vector<int>[Vertex+1];
    visit = new int[Vertex+1];
    for (int i = 1; i <= Vertex; i++) {
        visit[i] = 0;
    }
    for (int i = 0; i < Edge; i++) {
        cin >> src_ver >> dst_ver;
        course[src_ver].push_back(dst_ver);
        course[dst_ver].push_back(src_ver);    // 양 방향 그래프이기때문에 양쪽 모두에 넣어줌
    }
    BFS(1);    // 1번 vertex에서 각 vertex로 가는 경로를 BFS를 이용해 탐색
    for (int i = 1; i <= Vertex; i++) {
        cout << "Vectex Number : " << i << ", 1번 Vertex에서의 깊이 : " << visit[i] << endl;
    }
}
 
/*
    Input case:
    7 8
    1 2
    1 3
    1 5
    2 7
    2 6
    3 6
    3 4
    4 5
*/

Vector를 사용해 인접리스트 방식으로 구현했다.

양방향 그래프에서의 BFS지만 적어놓은 Input case는 단방향이라고 해도 별 무리 없이 진행될 수 있다.

위 BFS Process에서 설명한 순서대로 진행된다. 1번 정점에서만 탐색을 진행했고 정점 방문 순서와 Vertex number에 따라 1번 Vertex에서의 거리를 출력하게 구현했다.

실행 결과