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

Table of Contents

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

안녕하세요, mj입니다! 오늘은 파이썬에서 그래프 데이터 구조에 대해 이야기해보려 합니다. 그래프는 다양한 분야에서 사용되며, 데이터 간의 관계를 표현하는 데 매우 유용한 구조입니다. 이 글에서는 그래프의 개념, 구현 방법, 그리고 몇 가지 예제를 통해 그래프 데이터 구조를 이해하는 데 도움을 드리겠습니다.

그래프 데이터 구조란?

그래프는 노드(또는 정점)와 엣지(또는 간선)로 구성된 데이터 구조입니다. 노드는 데이터를 저장하고, 엣지는 노드 간의 관계를 나타냅니다. 그래프는 방향성에 따라 방향 그래프와 비방향 그래프로 나뉘며, 가중치에 따라 가중 그래프와 무가중 그래프로 구분할 수 있습니다.

그래프의 기본 구현

파이썬에서 그래프를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 인접 리스트와 인접 행렬을 사용하는 것입니다.

1. 인접 리스트

인접 리스트는 각 노드에 연결된 노드를 리스트로 저장하는 방법입니다. 이 방법은 메모리를 효율적으로 사용할 수 있으며, 그래프의 밀도에 따라 성능이 달라집니다.

graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'D'],
        'D': ['B', 'C', 'E'],
        'E': ['D']
    }

2. 인접 행렬

인접 행렬은 노드 간의 관계를 2차원 배열로 표현하는 방법입니다. 이 방법은 간선의 존재 여부를 쉽게 확인할 수 있지만, 메모리 사용량이 많아질 수 있습니다.

adj_matrix = [        [0, 1, 1, 0, 0],
        [1, 0, 0, 1, 0],
        [1, 0, 0, 1, 0],
        [0, 1, 1, 0, 1],
        [0, 0, 0, 1, 0]
    ]

그래프의 예시

예제 1: BFS (너비 우선 탐색)

BFS는 그래프의 모든 노드를 탐색하는 알고리즘입니다. 아래는 BFS를 구현한 예제입니다.

from collections import deque

    def bfs(graph, start):
        visited = set()
        queue = deque([start])
        
        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                visited.add(vertex)
                queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
        
        return visited

    print(bfs(graph, 'A'))  # 결과: {'A', 'B', 'C', 'D', 'E'}

예제 2: DFS (깊이 우선 탐색)

DFS는 그래프를 깊게 탐색하는 알고리즘입니다. 아래는 DFS를 구현한 예제입니다.

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

    print(dfs(graph, 'A'))  # 결과: {'A', 'B', 'D', 'C', 'E'}

예제 3: 최단 경로 찾기 (다익스트라 알고리즘)

다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 방법입니다.

import heapq

    def dijkstra(graph, start):
        queue = []
        heapq.heappush(queue, (0, start))
        distances = {vertex: float('infinity') for vertex in graph}
        distances[start] = 0

        while queue:
            current_distance, current_vertex = heapq.heappop(queue)

            if current_distance > distances[current_vertex]:
                continue

            for neighbor, weight in graph[current_vertex].items():
                distance = current_distance + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    heapq.heappush(queue, (distance, neighbor))

        return distances

    weighted_graph = {
        'A': {'B': 1, 'C': 4},
        'B': {'A': 1, 'C': 2, 'D': 5},
        'C': {'A': 4, 'B': 2, 'D': 1},
        'D': {'B': 5, 'C': 1}
    }

    print(dijkstra(weighted_graph, 'A'))  # 결과: {'A': 0, 'B': 1, 'C': 3, 'D': 4}