BFS, DFS

1. BFS와 DFS의 개념

 1) BFS

먼저 BFS는 영어로 풀어쓰면 Breath-First-Search로 너비 우선 탐색을 의미한다. 

 다음과 같은 그래프가 주어졌을 때 BFS의 방식으로 그래프 탐색을 어떻게 하는지 알아보자. 먼저 기준 노드를 잡아야한다. 기준 노드는 쉽게 말하면 탐색을 시작하는 노드을 의미한다. 편의상 1번 노드를 기준으로 탐색을 시작하자. BFS 로 탐색하면 아래와 같은 결과가 나온다.

1 - 2 - 4 - 5 - 3 - 6 - 7

 BFS는 기준노드와 거리가 가까운 노드들부터 탐색을 한다고 봐도 무방하다. 

 

 2) DFS

다음으로 DFS는 Depth-First-Search로 깊이 우선 탐색을 의미한다.

아까와 같은 그래프가 주어져있고 1번 정점부터 탐색을 시작한다고 할 때 탐색 결과는 아래와 같다.

1 - 2 - 3 - 4 - 5 - 6 - 7

 DFS는 시작 노드에서 인접한 노드들을 탐색하는데 어떤 인접 노드의 리프노드까지 완전히 탐색을 하고 다음 인접 노드를 탐색하는 방식이다.

 

2. BFS와 DFS의 구현

1) BFS

 BFS는 queue 자료 구조를 이용하여 구현한다. 알고리즘은 다음과 같다.

1) 시작노드 방문 처리 & queue에 넣음
2) queue가 비어 있을 때까지 3)~4) 반복(while)
3) queue의 Front를 꺼내고 방문 처리
4) 3)의 노드와 인접한 노드들 중 방문이 되어있지 않은 노드들을 모두 queue에 넣음

이를 코드로 구현하면 아래와 같다.

void BFS(int V){
    queue<int> q;
    visited[V] = true; //V는 시작노드
    q.push(V);
    while(!q.empty()){
    	int x = q.front();
        q.pop();
        for(int i=0;i<graph[x].size();i++){
            int nx = graph[x][i];
            if(!visited[nx]) q.push(nx);
        }
    }
}

구현하고자 하는 것이 무엇인지에 따라 내부의 코드는 차이가 날 수 있지만 구조는 보통 저런 식이다. 만약 시작노드로부터 떨어진 거리를 알고 싶은 경우는 visited 배열을 쓰지 않고 거리를 비교하여 구현할 수도 있다. 

void BFS(int V){
    queue<int> q;
    d[V] = 0;
    q.push(V);
    while(!q.empty()){
    	int x = q.front();
        q.pop();
        for(int i=0;i<graph[x].size();i++){
            int nx = graph[x][i];
            if(d[nx] > d[x] + 1) {
                q.push(nx);
                d[nx] = d[x] + 1;
            }
        }
    }
}

 

2) DFS

 DFS는 BFS와 다르게 stack이나 재귀함수로 구현한다(사실 재귀함수가 stack구조라서 똑같음). 알고리즘은 다음과 같다.

1) 시작노드 방문 처리 & stack에 넣음
2) stack이 빌 때 까지 3)~4) 반복
3) stack의 top을 꺼내고 방문 처리
4) 3)의 노드와 인접한 노드를 중 방문이 되어있지 않은 노드들을 모두 stack에 넣음

BFS에서 queue 대신 stack을 사용했다는 점 빼고 다른 것이 없다. 이를 코드로 구현하면 아래와 같다.

void DFS(int V){ //stack 사용
    stack<int> s;
    visited[V] = true; //V는 시작노드
    s.push(V);
    while(!q.empty()){
    	int x = s.top();
        s.pop();
        for(int i=0;i<graph[x].size();i++){
            int nx = graph[x][i];
            if(!visited[nx]) s.push(nx);
        }
    }
}

void DFS(int x){ //재귀함수 사용
	for(int i=0;i<graph[x].size();i++){
    	int nx = graph[x][i];
        if(!visited[nx]){
        	visited[nx] = true;
            DFS(nx);
        }
    }
}