[알고리즘] DFS & BFS

목차

DFS (깊이 우선 탐색)

DFS (Depth-First Search)는 깊이 우선 탐색이라고도 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

 

DFS는 재귀나 스택을 이용해서 구현을 한다. DFS를 구현할 때 어떤 노드를 방문했었는지 꼭 검사를 해야 한다. 왜냐하면 이를 검사하지 않을 경우 무한루프에 빠질 수 있기 때문이다. 

 

보통 모든 노드를 방문하고자 할 때, DFS를 이용한다. 하지만, 검색 속도는 보통 BFS보다 느리다.

 

구현 방법 : 

 

1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다.

 

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

 

3. 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

이제 예시를 한번 보겠다. 다음과 같은 그래프가 있다고 가정해보겠다. 그리고 시작은 1번 노드에서 한다고 가정하겠다.

 

 

우선 탐색 시작 노드인 1번 노드를 스택에 삽입하고, 방문 처리한다.

 

 

1을 스택에 넣은 다음 아직 방문하지 않은 인접 노드인 2를 스택에 넣고 방문 처리한다.

 

 

2를 스택에 넣은 다음에 인접 노드인 7을 방문하지 않았으므로 7을 스택에 넣고 방문 처리한다.

 

 

7을 넣은 다음에 인접 노드인 6을 스택에 넣고 방문 처리한다. 

 

 

6은 인접 노드 중에 방문하지 않은 노드가 없으므로 가장 최근에 추가한 6을 스택에서 제거해준다. 

 

 

스택에서 가장 최근에 추가된 7의 방문하지 않은 인접 노드인 8을 스택에 넣고 방문 처리한다.

 

 

8도 인접 노드 중에 방문하지 않은 노드가 없으므로 8을 스택에서 제거해준다. 제거한 다음에 7, 그리고 2도 마찬가지로 인접 노드 중에서 방문하지 않은 노드가 없으므로 7과 2를 순서대로 스택에서 제거해준다.

 

 

스택 최상단 노드인 1중에서 3을 아직 방문하지 않았으므로 3을 스택에 넣고 방문 처리해준다.

 

 

3의 인접 노드인 4를 아직 방문하지 않았으므로 4도 마찬가지로 스택에 추가하고 방문 처리한다.

 

 

4의 모든 인접 노드들을 방문했으므로 4를 스택에서 제거해준다.

 

 

스택 최상단에 있는 3의 인접 노드인 5를 아직 방문하지 않았으므로 5를 스택에 넣고 방문 처리한다.

 

 

모든 노드들을 방문했다. 알고리즘대로 하면 스택에 남아있는 노드들의 모든 인접 노드들을 방문했기에 스택에서 제거가 되고 알고리즘은 종료된다.

 

따라서 DFS를 이용했을 때 방문했던 노드의 순서는 다음과 같다.

 

1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

 

 

DFS 코드

 

void dfs(int x) {
	visited[x] = true;  //방문 처리
    for (int i = 1; i <= V; i++) {
    	if (graph[x][i] == 1 && !visited[i]) {  //방문하지 않았고 인접노드 일 경우
        	dfs(i);
        }
    }
}

 

 

BFS (너비 우선 탐색)

BFS (Breadth-First Search)는 너비 우선 탐색이라고도 하며, 가까운 노드부터 탐색하는 알고리즘이다. 즉, 시작 노드에서 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 방법이다. 따라서, 깊게 탐색하기 전에 넓게 탐색하는 것이다.

 

BFS는 DFS와 달리 재귀 함수로 구현할 수 없다. 대신, BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다. 즉, 선입선출을 원칙으로 탐색한다는 것이다. 

 

BFS에서도 마찬가지로 구현할 때 어떤 노드를 방문했었는지 꼭 검사를 해야 한다. 마찬가지로 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.

 

구현 방법 : 

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.

 

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.

 

3. 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

이제 예시를 한번 보겠다. 다음과 같은 그래프가 있다고 가정해보겠다. 그리고 시작은 1번 노드에서 한다고 가정하겠다.

 

 

우선 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.

 

 

먼저 1번 노드를 방문 처리하고 큐에 넣었다. 그다음에 큐에서 노드를 꺼내 방문하지 않은 모든 인접 노드를 큐에 삽입하고 방문 처리를 한다. 즉, 2번 노드와 3번 노드를 큐에 넣고 방문 처리를 한다.

 

 

마찬가지로 2번 노드를 큐에서 제거하고 2의 방문하지 않은 인접 노드를 큐에 넣고 방문 처리한다. 즉, 7번 노드를 큐에 넣는다.

 

 

마찬가지로 큐 맨 위에 있는 3번 노드를 제거하고 방문하지 않은 인접 노드들을 (4, 5번 노드) 큐에 넣고 방문 처리한다. 

 

큐 맨 위에 있는 7을 제거하고 방문하지 않은 인접 노드들을 (6, 8번 노드) 큐에 넣고 방문 처리한다.

 

 

이다음에는 큐에 남아있는 노드들을 순서대로 제거되고 알고리즘이 종료된다.

 

따라서 BFS를 이용했을 때 방문했던 노드의 순서는 다음과 같다.

 

1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

 

DFS랑 BFS랑 비교했을 때 방문하는 노드의 순서가 다른 것을 확인할 수 있다.

 

 

BFS 코드

void BFS(int v, int start) {
	Queue<Integer> q = new LinkedList<>();  //큐 초기화
    boolean[] visited = new boolean[v+1];  //방문한 노드 체크하는 배열
    visited[start] = true;
    q.add(start);
    
    while (!q.isEmpty()) {
    	int now = q.poll();
        for (int i = 1; i <= v; i++) {
        	if (graph[now][i] == 1 && !visited[i]) { //방문하지 않은 인접 노드
            	visited[i] = true;
                q.add(i);
            }
        }
    }
}