그래프 자료구조 심화: 파이썬 구현 가이드

핵심 요약

파이썬으로 그래프를 구현할 때는 인접 리스트를 딕셔너리(Dictionary)로 표현하는 방법이 가장 직관적이고 효율적이다. 이를 기반으로, 그래프 CRUD 연산과 탐색·최단경로 알고리즘을 단계별로 구현·응용한다.

1. 기본 Graph 클래스 설계

class Graph:
    def __init__(self):
        # { vertex: {neighbor: weight, ...}, ... }
        self.adj = {}
 
    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = {}
 
    def add_edge(self, u, v, w=1, directed=False):
        # 정점 존재 확인 후 추가
        self.add_vertex(u); self.add_vertex(v)
        # 무방향/방향 간선 추가
        self.adj[u][v] = w
        if not directed:
            self.adj[v][u] = w
 
    def remove_edge(self, u, v, directed=False):
        self.adj[u].pop(v, None)
        if not directed:
            self.adj[v].pop(u, None)
 
    def remove_vertex(self, v):
        self.adj.pop(v, None)
        for nbrs in self.adj.values():
            nbrs.pop(v, None)
 
    def vertices(self):
        return list(self.adj.keys())
 
    def edges(self):
        es = []
        for u, nbrs in self.adj.items():
            for v, w in nbrs.items():
                es.append((u, v, w))
        return es
 
    def __str__(self):
        lines = [f"{u} -> {nbrs}" for u, nbrs in self.adj.items()]
        return "\n".join(lines)

2. 그래프 생성 예시

g = Graph()
# 무방향 간선
g.add_edge('A', 'B')
g.add_edge('A', 'C', w=2)
g.add_edge('B', 'D')
g.add_edge('C', 'D', w=3)
print("Vertices:", g.vertices())
print("Edges:", g.edges())
print(g)

3. 그래프 탐색 구현

3.1 너비 우선 탐색(BFS)

from collections import deque
 
def bfs(graph, start):
    visited = set([start])
    q = deque([start])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.adj[u]:
            if v not in visited:
                visited.add(v)
                q.append(v)
    return order
 
print("BFS:", bfs(g, 'A'))

3.2 깊이 우선 탐색(DFS)

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(start)
    order.append(start)
    for v in graph.adj[start]:
        if v not in visited:
            dfs(graph, v, visited, order)
    return order
 
print("DFS:", dfs(g, 'A'))

4. 최단 경로 알고리즘

4.1 다익스트라(Dijkstra)

import heapq
 
def dijkstra(graph, src):
    dist = {v: float('inf') for v in graph.adj}
    dist[src] = 0
    heap = [(0, src)]
    prev = {}
 
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph.adj[u].items():
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, prev
 
distances, predecessors = dijkstra(g, 'A')
print("Distances:", distances)

4.2 경로 재구성

def reconstruct_path(prev, src, dest):
    path = []
    u = dest
    while u != src:
        path.append(u)
        u = prev.get(u)
        if u is None:
            return []  # 경로 없음
    path.append(src)
    return path[::-1]
 
print("Path A→D:", reconstruct_path(predecessors, 'A', 'D'))

5. 추가 심화 과제

음수 가중치: Bellman–Ford 알고리즘 구현
최소 신장 트리: Prim/Kruskal 알고리즘 구현
그래프 순환 검출: DFS 재귀 호출 시 스택 추적
동적 그래프: 실시간 간선 삽입·삭제 성능 최적화

이로써 파이썬을 활용한 그래프 기본 구조부터 탐색, 최단 경로 구현까지 핵심 코드 패턴을 익힐 수 있다. 필요한 알고리즘을 추가하며 다양한 응용에 적용해보자.

⁂

시스매

탐색기

그래프 자료구조 심화_ 파이썬 구현 가이드