DFS와 BFS에 대해서와 인접 행렬과 인접 그래프에 대해서 정리하고, 한 문제를 통해서 이해해보자.

설명에 앞서 코드에 대한 기준을 정하고 시작하면 좋을 것 같아 아래 문제를 기준으로 설명하도록 하겠다.

위 문제의 예제 1번인 아래 입력을 기준으로 설명하도록 하겠다.

4 5 1
1 2
1 3
1 4
2 4
3 4

DFS (Depth-First Search)

DFS는 깊이 우선 탐색이라고 부르며, 깊은 부분부터 우선적으로 탐색하는 알고리즘이다.

DFS는 Stack 자료구조 혹은 재귀 함수를 이용하여 구현할 수 있다.

image.png

DFS로 위 예제를 탐색하게 되면 1 2 4 3 이라는 결과를 얻을 수 있다.

해당 노드에서 갈 수 있는 방향을 기준으로 가장 작은 노드를 선택해서 방문 처리하며 진행한다.

이를 반복하여 끝까지 도달한다.

구현

Stack

private static void DFS_Stack(int start) {
    Stack <Integer> stack = new Stack();
    stack.add(start);

    while(!stack.isEmpty()) {
        int node = stack.pop();

        if (!visited[node]) {
            System.out.print(node + " ");
            visited[node] = true;
        }

        for (int next : adjList.get(node)) {
            if (visited[next]) continue;
            stack.add(next);
        }
    }
}