그래프는 현실 세계의 복잡한 관계를 표현하는 데 사용되는 자료 구조입니다. 그래프 순회는 그래프의 모든 노드 또는 일부 노드를 방문하는 프로세스를 의미합니다. 이러한 알고리즘은 다양한 문제를 해결하는 데 사용됩니다. 이번 블로그 포스트에서는 그래프 순회 알고리즘을 간단하게 소개하고, Python을 사용하여 구현하는 방법을 알아보겠습니다.

깊이 우선 탐색 (Depth-First Search)

깊이 우선 탐색 (Depth-First Search, DFS)은 그래프 순회의 한 종류로, 한 노드에서 시작하여 가능한 한 깊이 탐색을 진행한 후, 더 이상 탐색할 수 없을 때까지 백트래킹하여 다른 경로를 탐색합니다.

DFS를 구현하기 위해서는 스택을 사용할 수 있습니다. 아래는 DFS를 사용하여 그래프를 순회하는 Python 코드의 예시입니다.

def dfs(graph, start_node):
    visited = set()  # 방문한 노드를 저장하기 위한 집합
    stack = [start_node]  # 스택에 시작 노드를 추가

    while stack:
        current_node = stack.pop()  # 스택에서 노드를 꺼냄

        if current_node not in visited:
            visited.add(current_node)  # 현재 노드를 방문한 노드로 추가

            # 현재 노드와 연결된 모든 이웃 노드를 스택에 추가
            stack.extend(graph[current_node] - visited)

    return visited

위 코드에서 graph는 그래프를 나타내는 딕셔너리이며, 각 노드는 집합으로 표현됩니다. 시작 노드로부터 DFS를 수행하고, 방문한 노드를 집합 visited에 추가하여 순회 결과를 반환합니다.

너비 우선 탐색 (Breadth-First Search)

너비 우선 탐색 (Breadth-First Search, BFS)은 다른 하위 노드를 방문하기 전에 현재 노드의 모든 이웃 노드를 방문하는 그래프 순회 알고리즘입니다.

BFS를 구현하기 위해서는 큐를 사용할 수 있습니다. 아래는 BFS를 사용하여 그래프를 순회하는 Python 코드의 예시입니다.

from collections import deque

def bfs(graph, start_node):
    visited = set()  # 방문한 노드를 저장하기 위한 집합
    queue = deque([start_node])  # 큐에 시작 노드를 추가

    while queue:
        current_node = queue.popleft()  # 큐에서 노드를 꺼냄

        if current_node not in visited:
            visited.add(current_node)  # 현재 노드를 방문한 노드로 추가

            # 현재 노드와 연결된 모든 이웃 노드를 큐에 추가
            queue.extend(graph[current_node] - visited)

    return visited

위 코드에서 graph는 그래프를 나타내는 딕셔너리이며, 각 노드는 집합으로 표현됩니다. 시작 노드로부터 BFS를 수행하고, 방문한 노드를 집합 visited에 추가하여 순회 결과를 반환합니다.

정리하자면, 그래프 순회 (탐색) 알고리즘은 그래프의 모든 노드를 방문하는 프로세스입니다. 깊이 우선 탐색과 너비 우선 탐색은 그래프 순회를 수행하는 두 가지 주요 알고리즘입니다. 이를 Python으로 구현하면 다양한 그래프 문제를 해결할 수 있습니다.