DFS, BFS

해당 내용은 '파이썬 알고리즘 인터뷰'를 참고하여 작성하였다.

그래프의 각 정점을 방문하는 그래프 순회에는 크게 깊이 우선 탐색 (Depth-First Search, DFS)과 너비 우선 탐색 (Breadth-First Search, BFS)의 2가지 알고리즘이 있다.

우선, 파이썬으로 그래프를 표현하는 방법에는 인접 리스트 등이 있는데, 출발 노드를 키로, 도착 노드를 값으로 표현할 수 있다. 도착 노드는 여러 개일 수 있어 리스트 형태가 된다.

위 그래프를 파이썬의 딕셔너리 자료형으로 나타내면 다음과 같다.

graph = { 1: [2, 3, 4], 2: [5], 3: [5], 4: [], 5: [6, 7], 6: [], 7: [3], }

DFS (깊이 우선 탐색)

일반적으로 DFS는 스택 혹은 재귀로 구현할 수 있다.

#재귀 구조로 구현
def recursive_dfs(v, discovered = []):
	discovered.append(v)
    for w in graph[v]: #위에 작성한 graph
    	if w not in discovered:
        	discovered = recursive_dfs(w, discovered)
    return discovered
    
recursive_dfs(1)
>>[1, 2, 5, 6, 7, 3, 4]

해당 코드는 막다른 곳이 도달할 때까지 연속으로 진행되므로, 1->2->5->6(->5)->7->3(->7->5->2->1->3)->4 순으로 탐색하게 된다.

#스택을 이용한 반복 구조로 구현
def iterative_dfs(start_v):
	discovered = []
    stack = [start_v]
    while stack:
    	v = stack.pop()
       	if v not in discovered:
        	discovered.append(v)
            for w in graph[v]:
            	stack.append(w)
    return discovered

iterative_dfs(1)
>> [1, 4, 3, 5, 7, 6, 2]

같은 DFS인데 순서가 다른 이유는 재귀 DFS는 사전식 순서로 방문한 데 반해 스택 반복 DFS는 역순으로 방문하였다. stack.pop()으로 가장 마지막에 삽입된 노드부터 먼저 꺼내서 discovered 배열에 저장되므로 이러한 결과가 나오게 된다.

BFS (너비 우선 탐색)

일반적으로 BFS는 큐를 이용한 반복 구조로 구현한다. 재귀로는 동작하지 않는다.

#큐를 이용한 반복 구조로 구현
def iterative_bfs(start_v):
	discovered = [start_v]
    queue = [start_v]
    while queue:
    	v = queue.pop(0)
        for w in graph[v]:
        	if w not in discovered:
            discovered.append(w)
            queue.append(w)
    return discovered

iterative_bfs(1)
>> [1, 2, 3, 4, 5, 6, 7]

1부터 순서대로 각각의 인접 노드를 우선으로 방문하는 너비 우선 탐색이 잘 실행되었다.