[알고리즘] 그래프 순회(Graph Traversal)

그래프 순회란?

그래프 순회란 그래프 탐색(Search)라고도 일컫으며 그래프의 각 정점을 방문하는 과정을 의미하며, 크게 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)으로 나뉜다. DFS는 주로 스택이나 재귀로 구현하며 백트래킹 알고리즘에 사용된다. 반면에 BFS는 주로 큐로 구현하며 그래프의 최단 경로를 구하는 문제 등에 사용된다.

 

DFS vs BFS

 

깊이 우선 탐색(DFS)

일반적으로 DFS는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. 실제로 코딩 테스트에서는 재귀를 이용한 구현이 더 선호되는 편이다.

 

 

Iteration DFS vs Recursion DFS

재귀적 구조로 구현

먼저 재귀 구조로 DFS를 구현해보자. 슈도코드는 다음과 같다.

RecursiveDFS(v)
    mark v as visited node
    for each edge (v, w)
        if w is unmarked
            RecursiveDFS(w)

이를 실제로 구현하면 다음과 같다.

def recursive_dfs(v, visited=[]):
    visited.append(v)
    for w in graph[v]:
    	if not w in visited:
        	visited = recursive_dfs(w, visited)
    return visited

이렇게 재귀적으로 DFS를 구현하게 되면 모든 정점을 사전식 순서(A->B->C..)로 방문하게 된다.

스택을 이용한 반복 구조로 구현

이번에는 스택을 이용해 반복 구조로 DFS를 구현해보자. 코드는 다음과 같다.

# Pseudo Code
IterativeDFS(s)
    stack.push(s)
    while stack is not empty
        v = stack.pop()
        if v is unmarked
            mark v as visited node
            for each edge v → w
                if w is unmarked
            		stack.push(w)

 

def iterative_dfs(s):
    visited = []
    stack = [s]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)
    return visited

이렇게 스택을 이용해 구현한 DFS는 재귀 구조에 비해 코드의 간결함은 떨어지지만, 실행 속도는 더 빠른 편이다. 또한, 재귀 DFS와 달리 모든 정점을 역순(C->B->A..)으로 방문하게 된다.

 

 

너비 우선 탐색(BFS)

BFS는 DFS보다 적게 쓰이지만, 최단 경로를 찾는 문제나 다익스트라 알고리즘 등에서 유용하게 사용된다. 

큐를 이용한 반복 구조로 구현

스택을 이용하는 DFS와 달리, BFS를 반복 구조로 구현할 때는 큐를 이용한다. 코드는 다음과 같다.

# Pseudo Code
BFS(s):
    mark s as visited node
    Q.enqueue(s)
    while Q is not empty:
        v = Q.dequeue()
        for each edge v → w:
            if w is unmarked:
                mark v as visited node
                Q.enqueue(w)
                # w.parent = v
                # w.dist = v.dist + 1

def iterative_bfs(s):
    visited = [s]
    queue = [s]
    while queue:
        v = queue.pop(0)  # v = deque.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                queue.append(w)
    return visited

BFS는 DFS와 달리 재귀로 동작하지 않기 때문에 큐를 이용한 반복 구조로만 구현이 가능하다. 이 점을 유의해야 한다.

 

참고

Data Structures with Python(신찬수 저)

파이썬 알고리즘 인터뷰(박상길 저)