[알고리즘] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

DFS (깊이 우선 탐색, Depth First Search)

DFS는 그래프에서 깊은 부분을 우선적으로 탐색합니다.

한 정점에서 시작해 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다.

 

특징

• 스택 자료 구조에 기초하며, 구현할 때 재귀 함수로 구현하는 것이 좀더 간편합니다.
• DFS를 구현할 때, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 검사하지 않을 시 무한 루프에 빠질 위험이 있으므로 반드시 검사해야합니다. ( visited[index] = true; )

• 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다.
• 모든 경우를 하나하나 다 탐색을 해야될경우 사용합니다. ( 순열, 조합 구현 )
• 검색 속도 자체는 BFS에 비해 느립니다.

 

탐색 과정

( 파란색 : 이동방향, 초록색 : 탐색 순서 ) 

1. 제일 상위 노드 "1"부터 시작하여 방문하지 않은 인접한 "2, 3"노드 중 가장 작은 노드 "2"를 방문합니다. ( 1 -> 2 )
2. "2"에서 방문하지 않은 인접한 노드 "4"를 방문합니다. ( 1 -> 2 -> 4 )
3. "4"에서 인접한 노드는 "2번"노드 인데 이미 방문한 노드이므로 "4"번 노드를 호출한 부모 노드 "2"로 돌아갑니다.
4. "2"에서 인접한 노드는 "1, 4"인데 둘 다 이미 방문한 노드이므로 "2"번 노드를 호출한 부모 노드 "1"로 돌아갑니다.
5. "1"번 노드와 인접한 노드는 "2, 3"인데 2번은 이미 방문 하였으므로 방문하지 않은 "3"번 노드를 방문합니다. ( 1 -> 2 -> 4 -> 3 )
6. "3"번 노드와 인접한 노드는 "5, 6"인데 둘다 방문하지 않았으므로 가장 작은 노드 "5"번 노드를 방문합니다. ( 1 -> 2 -> 4 -> 3 -> 5 )
7. "5"번 노드와 인접한 "7"번 노드를 방문합니다. ( 1 -> 2 -> 4 -> 3 -> 5 -> 7 )
8. "7"번 노드에 더이상 인접한 노드가 없으므로 부모 노드 "5"로 돌아가고 "5"도 "7"을 이미 방문했으므로 부모 노드 "3"으로 돌아갑니다.
9. "3"번 노드에서 방문하지 않은 "6"번 노드를 방문합니다. ( 1 -> 2 -> 4 -> 3 -> 5 -> 7 -> 6 ) 
10. 역순으로 돌아가 방문하지 않은 노드가 있는지 확인하고 다 방문했다면 해당 방문 순서로 탐색 결과를 반환하고 종료합니다.

탐색 순서 : 1 -> 2 -> 3 -> 4 -> 5 ->  7 -> 6

 

구현 코드

public class Dfs {
    public static void main(String[] args) {
        int start = 1; // 시작 노드
        dfs(start);
    }

    // 각 노드가 연결상태를 2차원 배열로 표현
    // 해당 graph의 인덱스번호의 배열은 해당 노드에서 연결된 노드를 갖는다.
    //                      0번  1번    2번    3번     4번    5번   6번   7번
    static int[][] graph = {{}, {2, 3}, {4}, {5, 6}, {2}, {5, 7}, {3}, {7}};

    // 방문처리에 사용 할 배열
    static boolean[] visited = new boolean[graph.length];

    static void dfs(int index) {
        // 현재 노드를 방문 처리
        visited[index] = true;

        // 방문 노드 출력
        System.out.print(index + " -> ");

        // 방문한 노드에 인접한 노드 찾기
        for (int node : graph[index]) {
            // 인접한 노드가 방문한 적이 없다면 재귀 호출
            if(!visited[node]) {
                dfs(node);
            }
        }
    }
}

---

BFS (너비 우선 탐색, Bread First Search )

BFS는 그래프에서 가장 가까운 부분을 우선적으로 탐색합니다.

한 정점에서 가장 인접한 노드를 먼저 넓게 탐색하면서 깊이 내려가므로 DFS와는 정반대입니다.

 

특징

• 재귀적으로 동작하지 않습니다.
• BFS도 DFS처럼 노드 방문 여부를 반드시 검사해야합니다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 선입 선출 자료구조 Queue를 사용합니다. (선입선출 원칙으로 탐색)
• 최단경로(다익스트라, 플로이드)를 찾는데 활용합니다.

 

탐색 과정

( 파란색 : 이동방향, 초록색 : 탐색 순서 ) 

1. 제일 상위 "1"번노드에서 시작하여 "1"번 노드를 큐에 넣고 방문 처리합니다.
2. "1"번 노드와 인접한 "2, 3"번 노드를 큐에 넣고 방문 처리 합니다. ( 2 , 3 )
3. 큐에서 "2"번 노드를 꺼내고 "2"번 노드와 인접한 방문하지 않은  "4"번 노드를 큐에 넣고 방문 처리 합니다. ( 3, 4 )
4. 큐에서 "3"번 노드를 꺼내고 "3번" 노드와 인접한 방문하지 않은 "5, 6"번 노드를 큐에 넣고 방문 처리 합니다. ( 4, 5, 6 ) 
5. 큐에서 "4"번 노드를 꺼내고 방문하지 않은 인접한 노드가 없으므로 넘어갑니다. ( 5, 6 )
6. 큐에서 "5"번 노드를 꺼내고 "5"번과 인접한 방문하지 않은 "7"번 노드를 큐에 삽입하고 방문 처리 합니다. ( 6, 7 )
7. 큐에서 "6"번 노드를 꺼내고 방문하지 않은 인접한 노드가 없으므로 넘어 갑니다. ( 7 )
8. "7"번 노드도 인접한 노드가 없으므로 큐에서 꺼냅니다.

탐색 순서 ( 큐에 들어간 순서 ) : 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 

 

구현 코드

import java.util.LinkedList;
import java.util.Queue;

public class Bfs {
    public static void main(String[] args) {
        // 각 노드가 연결상태를 2차원 배열로 표현
        int[][] graph = {{}, {2, 3}, {4}, {5, 6}, {2}, {5, 7}, {3}, {7}};

        // 방문처리에 사용 할 배열
        boolean[] visited = new boolean[graph.length];

        // 시작 노드
        int start = 1;

        // 큐 생성
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        // 현재 노드를 방문 처리
        visited[start] = true;

        // 큐가 비었을 때 까지 반복
        while (!queue.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int node = queue.poll();
            System.out.print(node + " -> ");

            // 인접한 노드 중 아직 방문하지 않은 원소들을 큐에 삽입
            for (int index : graph[node]) {
                if (!visited[index]) {
                    queue.add(index);
                    visited[index] = true;
                }
            }
        }
    }
}