파이썬에서 그래프 데이터 구조 활용하기 – mj의 블로그

Table of Contents

파이썬에서 그래프 데이터 구조 활용하기

안녕하세요, mj입니다! 오늘은 파이썬에서 그래프 데이터 구조를 활용하는 방법과 다양한 사례에 대해 알아보겠습니다. 그래프는 노드(정점)와 엣지(간선)로 구성된 데이터 구조로, 여러 분야에서 유용하게 사용됩니다. 그럼 시작해볼까요?

그래프 데이터 구조란?

그래프는 수학적으로 정의된 데이터 구조로, 객체 간의 관계를 표현합니다. 예를 들어, 소셜 네트워크에서 사용자 간의 연결을 나타내거나, 도로 네트워크에서 도로 간의 연결을 나타낼 수 있습니다.

파이썬에서 그래프 구현하기

파이썬에서는 그래프를 여러 방법으로 구현할 수 있습니다. 가장 일반적인 방법은 딕셔너리나 리스트를 사용하는 것입니다. 다음은 간단한 그래프 구현 예시입니다:


# 그래프를 딕셔너리로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

그래프 탐색 알고리즘

그래프를 탐색하는 알고리즘에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 각각의 알고리즘을 구현해 보겠습니다.

1. 깊이 우선 탐색 (DFS)


def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# DFS 실행
result_dfs = dfs(graph, 'A')
print(result_dfs)  # 출력: {'A', 'B', 'C', 'D', 'E', 'F'}

2. 너비 우선 탐색 (BFS)


from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

# BFS 실행
result_bfs = bfs(graph, 'A')
print(result_bfs)  # 출력: {'A', 'B', 'C', 'D', 'E', 'F'}