DFS(깊이 우선 탐색)

Depth-First Search의 약자로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

그래프는 노드(Node)/정점(Vertex)과 간선(Edge)로 구성되는데 그래프를 표현하는 방법으로는 인접 행렬, 인접 리스트가 있다. 인접 행렬은 NxN 행렬을 만들어서 i번째 노드에서 j번째 노드로 갈 수 있다면 1을 표시, 갈 수 없다면 0을 표시하는 것이 일반적이다. 인접 리스트의 i번째 원소는 i번째 노드에서 갈 수 있는 노드들을 담고 있다.

DFS를 파이썬으로 나타낸 코드는 다음과 같다. 시간복잡도는 인접 리스트로 나타냈을 때 $O(V + E)$에 해당한다. (인접 행렬은 $O(V^{2})$)

# 인접 리스트
graph = [
    [1, 2],
    [0, 3],
    [0],
    [3]
]
# 방문 여부
visited = [False] * len(graph)
stack = []


def dfs(i, visited, stack):
    stack.append(i)
    visited[i] = True
    for j in graph[i]:
        if not visited[j]:
            dfs(j, visited, stack)


dfs(0, visited, stack)
print(*stack) # 0 1 3 2

BFS(너비 우선 탐색)

BFS를 수행할 때는 선입선출의 특성을 띠는 큐 자료구조를 사용한다. BFS의 중요한 특징은 한 노드에서 다른 노드로 가는 최단거리를 항상 구한다는 것이다.

BFS를 파이썬으로 나타낸 코드는 다음과 같다. 시간복잡도는 인접 리스트로 나타냈을 때 $O(V + E)$에 해당한다. (인접 행렬은 $O(V^{2})$)

from collections import deque


# 인접 리스트
graph = [
    [1, 2],
    [0, 3],
    [0],
    [3]
]
# 방문 여부
visited = [False] * len(graph)
stack = []


def bfs(start, visited, stack):
    q = deque([start])
    while q:
        now = q.popleft()
        visited[now] = True
        stack.append(now)
        for j in graph[now]:
            if not visited[j]:
                q.append(j)
    

bfs(0, visited, stack)
print(*stack) # 0 1 2 3