탐색 알고리즘 - DFS, BFS

DFS (Depth-Fisrt Search)

DFS: 깊이 우선 탐색

트리 상에서 자식 노드가 있다면, 아래(자식 노드)로 계속 전진하여 탐색하는 방법.

위 그림에서 각 노드의 번호는 탐색 순서를 뜻한다. 1번 노드는 2, 5번 노드를 자식으로 가진다. 하지만 2번 노드가 자식 노드를 가지기 때문에 5번 노드를 탐색하기 전 3, 4번 노드를 우선 탐색한다. 2번 노드에 다른 자식 노드가 없기 때문에 다시 5번 노드를 탐색하는 형태이다. 

 

구현 - Python

- open 리스트: 탐색하지 않은 상태(노드)들

- close 리스트: 탐색을 마친 상태(노드)들

DFS는 스택(stack)을 이용하여 구현할 수 있다. (FILO)

def dfs(graph, start_node):

    # open list: stack, close list
    need_visit, visited = list(), list()
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited

open 리스트와 close 리스트를 생성한다. 첫 노드를 탐색한 후, 하위 노드를 open 리스트에 추가한다. open 리스트는 스택 형태로, 스택의 마지막 값을 제거한 후 하위 노드를 다시 스택에 추가한다. 다만, close 리스트에 포함된 노드는 무시된다. 

예제:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"],
}

dfs(graph, "A")

결과:

1
open: ['B', 'C']
close: ['A']
2
open: ['B', 'A', 'F']
close: ['A', 'C']
3
open: ['B', 'A', 'C']
close: ['A', 'C', 'F']
4
open: ['B', 'A']
close: ['A', 'C', 'F']
5
open: ['B']
close: ['A', 'C', 'F']
6
open: ['A', 'D', 'E']
close: ['A', 'C', 'F', 'B']
7
open: ['A', 'D', 'B']
close: ['A', 'C', 'F', 'B', 'E']
8
open: ['A', 'D']
close: ['A', 'C', 'F', 'B', 'E']
9
open: ['A', 'B']
close: ['A', 'C', 'F', 'B', 'E', 'D']
10
open: ['A']
close: ['A', 'C', 'F', 'B', 'E', 'D']
11
open: []
close: ['A', 'C', 'F', 'B', 'E', 'D']

각 과정을 보면 open 리스트의 마지막 항목을 제거한 후, 해당 항목과 연결된 모든 항목을 리스트에 추가한다. 그리고 제거된 항목은 close 리스트로 이동한다. 다만, 3번 항목의 'C'처럼 이미 close에 포함되어 있는 항목은 무시된다. 

---

BFS (Breadth-First Search)

BFS: 넓이 우선 탐색

트리 상에 자식 노드가 있다면 모든 자식 노드를 탐색한 후, 다음 레벨의 노드를 탐색한다. 

위 그림에서 파랑 노드를 먼저 탐색한 후, 파랑 노드의 자식 노드인 초록 노드를 모두 탐색한다. 그리고 초록 노드의 자식 노드인 남색 노드를 모두 탐색하게 된다.

 

구현 - Python

BFS는 자식 노드들이 들어오면 바로 탐색하기 때문에 큐를 사용한다. (FIFO)

def bfs(graph, start_node):
    # open list: queue
    visited, need_visit = list(), list()
    need_visit.append(start_node)

    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited

각 노드를 탐색하며 해당 노드의 자식 노드가 있는지 확인한다. 자식 노드들을 탐색하면서, 자식 노드들과 연결된 노드들을 다시 open 리스트에 추가한다. 해당 과정을 반복하며 탐색을 진행한다.

예제:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"],
}

bfs(graph, "A")

결과:

1
open: ['B', 'C']
close: ['A']
2
open: ['C', 'A', 'D', 'E']
close: ['A', 'B']
3
open: ['A', 'D', 'E', 'A', 'F']
close: ['A', 'B', 'C']
4
open: ['D', 'E', 'A', 'F']
close: ['A', 'B', 'C']
5
open: ['E', 'A', 'F', 'B']
close: ['A', 'B', 'C', 'D']
6
open: ['A', 'F', 'B', 'B']
close: ['A', 'B', 'C', 'D', 'E']
7
open: ['F', 'B', 'B']
close: ['A', 'B', 'C', 'D', 'E']
8
open: ['B', 'B', 'C']
close: ['A', 'B', 'C', 'D', 'E', 'F']
9
open: ['B', 'C']
close: ['A', 'B', 'C', 'D', 'E', 'F']
10
open: ['C']
close: ['A', 'B', 'C', 'D', 'E', 'F']
11
open: []
close: ['A', 'B', 'C', 'D', 'E', 'F']

DFS와 달리 open 리스트에 먼저 입력된 값을 우선 탐색한다. 그렇기 때문에 높은 수준의 노드들이 먼저 탐색되는 형태이다. 다만 3번의 'A'와 같이 close 리스트에 이미 포함된 값은 무시된다.