[알고리즘/Algorithm] 파이썬으로 깊이 우선 탐색 DFS / 너비 우선 탐색 BFS 알아보기

그래프를 탐색하는 방법은 대표적으로 DFS (깊이 우선 탐색)와 BFS (너비 우선 탐색)가 있다.

 

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

임의의 노드에서 시작해서 다음 브랜치로 넘어가기 전에 해당 브랜치를 완벽하게 탐색하며 모든 노드를 탐색하는 방법

 

 

 

위와 같은 그래프를 깊이 우선 탐색으로 탐색한다고 하면 아래와 같은 탐색 순서가 나타난다. 

깊이 우선 탐색은 위 그림과 같이 임의의 노드부터 시작하여 해당 노드의 브랜치를 전부 탐색한 이후에 다른 브랜치로 넘어가 탐색하며 모든 노드를 탐색할 때까지 반복한다.

 

1-1. 깊이 우선 탐색 구현

 

파이썬 코드로 나타낸 그래프

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'G', 'H', 'I'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
    'G': ['C'],
    'H': ['C'],
    'I': ['C', 'J'],
    'J': ['I']
}

위에서 살펴본 예시 그래프를 파이썬의 딕셔너리 형태로 표현하면 이렇게 표현할 수 있다. 

 

A는 B랑 C와 연결되어 있고,

B는 A랑 D와 연결되어 있고, 

...

J는 I와 연결되어 있다.

 

DFS 파이썬 코드

def dfs(graph, start):
    visited, need_visit = [], []

    need_visit.append(start)

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

    return visited

 

우선 방문한 노드(visited)와 방문해야 될 노드들(need_visit)을 나타낼 리스트 두 개를 초기화 해준다.

 

그리고 탐색을 시작할 노드를 need_visit에 apped 해준다. 

 

이후에 while문을 반복하면서 본격적인 탐색을 반복한다.

need_visit.pop()을 통해 node를 할당 받고, 

해당 node가 visited에 존재하지 않으면 visited에 추가해준다.

 

그 후 need_visit에 추가로 탐색해야 될 node를 

need_visit.extend(graph[node]) 이 구문으로 추가해준다.

 

 

깊이 우선 탐색 결과

['A', 'C', 'I', 'J', 'H', 'G', 'B', 'D', 'F', 'E']

 

2. 너비 우선 탐색 (BFS, Breadth-First Search)

임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하며 모든 노드를 탐색하는 방법

 

깊이 우선 탐색에서 예시로 사용한 그래프를 똑같이 사용하여 너비 우선 탐색을 하게 되면 위와 같은 순서로 탐색을 하게 된다.

A부터 시작하여 마지막 레벨로 도달할 때까지 같은 레벨에 있는 노드부터 순차적으로 탐색한다.

 

BFS 파이썬 코드

def bfs(graph, start):
    visited, need_visit = [], []

    need_visit.append(start)

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

    return visited

DFS의 코드와 비교하여 다른점은 pop()이 pop(0)으로 바뀐 점 밖에 없다.

다른 점은 pop 부분 밖에 없기 때문에 위에서 설명한 DFS와 비교하면 금방 이해할 수 있을 것이다.

 

 

너비 우선 탐색 결과

['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

깊이 우선 탐색에서 예시로 든 그래프를 똑같이 탐색한다고 하면 위와 같은 탐색 결과를 얻을 수 있다.