그래프 | Graph

Posted Apr 7, 2025 Updated Apr 8, 2025

By 맹

19 min read

그래프 | Graph

내가 볼려고 작성한 알고리즘 공부.

💾 그래프 (Graph)

✅ 1. 그래프란?

그래프(Graph)는 사물(정점, Node) 간의 관계(간선, Edge)를 표현하는 자료구조다. 정점은 사람, 도시, 컴퓨터처럼 무언가를 나타내는 단위이고, 간선은 그 정점 간의 연결 관계를 의미한다.

📌 그래프 용어 정리

용어	의미
정점(Vertex)	노드(Node), 데이터 단위 객체
간선(Edge)	두 정점을 연결하는 선
인접(Adjacent)	두 정점이 간선으로 연결됨
무방향 그래프	간선이 양방향 (A-B면 B-A도 가능)
방향 그래프	간선에 방향 있음 (A→B)
가중치(Weight)	간선에 부여된 비용 또는 거리

그래프는 지도, SNS 친구 관계, 네트워크, 작업 순서, 게임 맵 등 다양한 분야에서 활용된다.

✅ 2. 그래프의 표현 방식

2.1 인접 리스트 (Adjacency List)

각 노드가 연결된 노드들의 목록을 리스트로 저장하는 방식. 간선이 적은 희소 그래프에 효율적.

  
n = 5  # 노드 수
graph = [[] for _ in range(n+1)]
graph[1].append(2)
graph[1].append(3)

공간 복잡도: O(N + M) (N: 노드 수, M: 간선 수)
특정 간선 존재 여부 확인은 느림

2.2 인접 행렬 (Adjacency Matrix)

노드 간의 연결 여부를 2차원 배열로 저장. 모든 간선 정보를 빠르게 확인할 수 있지만 공간 낭비가 큼.

  
n = 5  # 노드 수
graph = [[0] * (n+1) for _ in range(n+1)]
graph[1][2] = 1  # 1번 노드에서 2번 노드로 연결됨

공간 복잡도: O(N²)
간선 확인은 빠름 (O(1))

✅ 3. 최단 경로 알고리즘

그래프에서 최단 거리(Shortest Path) 를 구하는 대표적인 알고리즘들을 정리합니다.
상황에 따라 어떤 알고리즘을 써야 하는지 빠르게 판단할 수 있도록 구성했습니다.

1. 다익스트라 (Dijkstra)

하나의 시작 정점에서 모든 정점까지의 최단 거리
모든 간선 가중치 ≥ 0 (음수 불가)

전략: 가장 가까운 정점부터 확정
우선순위 큐 (heapq)로 구현
중복 방문 가능하지만 더 짧은 경로만 갱신함

시간 복잡도:

배열: O(V²)
heapq 사용: O(E log V)

사용 예시:

  
import heapq

def dijkstra(start, graph, n):
    INF = int(1e9)
    distance = [INF] * (n + 1)
    distance[start] = 0
    heap = [(0, start)]

    while heap:
        dist, now = heapq.heappop(heap)
        if distance[now] < dist:
            continue
        for neighbor, weight in graph[now]:
            cost = dist + weight
            if cost < distance[neighbor]:
                distance[neighbor] = cost
                heapq.heappush(heap, (cost, neighbor))
    return distance

제한 사항:

❌ 음수 간선이 하나라도 있으면 부정확

2. 벨만-포드 (Bellman-Ford)

하나의 시작 정점에서 모든 정점까지의 최단 거리
음수 간선 가능, 음수 사이클 탐지 가능

전략: 모든 간선을 V-1번 반복해서 완화
V번째 반복에서 또 갱신되면 → 음수 사이클 존재

시간 복잡도:

O(V × E)

사용 예시:

  
def bellman_ford(start, edges, n):
    INF = int(1e9)
    distance = [INF] * (n + 1)
    distance[start] = 0

    for _ in range(n - 1):
        for u, v, cost in edges:
            if distance[u] + cost < distance[v]:
                distance[v] = distance[u] + cost

    # 음수 사이클 탐지
    for u, v, cost in edges:
        if distance[u] + cost < distance[v]:
            return None  # 음수 사이클 존재
    return distance

장점:

단순한 구조로 구현 쉬움
사이클 유무 판단까지 가능

단점:

느리다

3. SPFA (Shortest Path Faster Algorithm)

벨만-포드의 실용적 개선 알고리즘

큐(Queue) 기반으로, 필요한 정점만 갱신
보통은 매우 빠르지만, 최악의 경우는 벨만-포드와 동일

시간 복잡도:

평균: O(E) 수준
최악: O(V × E)

사용 예시:

  
from collections import deque

def spfa(start, graph, n):
    INF = int(1e9)
    distance = [INF] * (n + 1)
    in_queue = [False] * (n + 1)
    count = [0] * (n + 1)
    
    distance[start] = 0
    queue = deque([start])
    in_queue[start] = True

    while queue:
        now = queue.popleft()
        in_queue[now] = False

        for neighbor, weight in graph[now]:
            if distance[now] + weight < distance[neighbor]:
                distance[neighbor] = distance[now] + weight
                if not in_queue[neighbor]:
                    queue.append(neighbor)
                    in_queue[neighbor] = True
                    count[neighbor] += 1
                    if count[neighbor] >= n:
                        return None  # 음수 사이클 존재
    return distance

장점:

벨만-포드보다 훨씬 빠름 (대부분 상황에서)

4. 플로이드-워셜 (Floyd-Warshall)

모든 정점 쌍 간의 최단 거리를 구함
2차원 배열 + 점화식 기반

전략: 중간 노드를 기준으로 거리 갱신
인접 행렬 사용, 공간 O(V²)

시간 복잡도:

O(V³)

사용 예시:

  
def floyd_warshall(n, edges):
    INF = int(1e9)
    dist = [[INF] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        dist[i][i] = 0

    for u, v, cost in edges:
        dist[u][v] = cost

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

장점:

간단하고 확실함
모든 쌍 최단 거리 한 번에 계산

단점:

느림 (V가 작을 때만 사용 가능)

5. Johnson’s Algorithm

모든 정점 쌍 간의 최단 거리 + 음수 간선 허용
(단, 음수 사이클은 없어야 함)

전략: 벨만-포드로 가중치 보정 → 다익스트라 여러 번 수행
희소 그래프에서 유용

시간 복잡도:

O(V² log V + VE)

사용 예시:

  
import heapq

def johnsons_algorithm(n, edges):
    INF = int(1e9)
    new_edges = edges + [(0, v, 0) for v in range(1, n + 1)]
    h = [0] * (n + 1)

    # Bellman-Ford to find potential h[v]
    for _ in range(n):
        for u, v, w in new_edges:
            if h[u] + w < h[v]:
                h[v] = h[u] + w

    # Reweight edges
    reweighted = []
    for u, v, w in edges:
        reweighted.append((u, v, w + h[u] - h[v]))

    # Run Dijkstra for each node
    def dijkstra(start):
        dist = [INF] * (n + 1)
        dist[start] = 0
        heap = [(0, start)]
        while heap:
            cost, u = heapq.heappop(heap)
            if cost > dist[u]:
                continue
            for v, w in graph[u]:
                if dist[v] > cost + w:
                    dist[v] = cost + w
                    heapq.heappush(heap, (dist[v], v))
        return dist

    # Build reweighted graph
    graph = [[] for _ in range(n + 1)]
    for u, v, w in reweighted:
        graph[u].append((v, w))

    result = []
    for i in range(1, n + 1):
        dist = dijkstra(i)
        # Reverse weight change
        result.append([d + h[v] - h[i] if d < INF else INF for v, d in enumerate(dist)])

    return result

장점:

플로이드-워셜보다 빠를 수 있음 (희소 그래프에서)

알고리즘 비교 요약표

알고리즘	대상	음수 간선	음수 사이클 탐지	시간 복잡도	주요 특징
다익스트라	단일 시작점	❌ 안 됨	❌ 안 됨	O(E log V)	양수 간선 전용, 빠르고 효율적
벨만-포드	단일 시작점	✅ 가능	✅ 가능	O(V × E)	단순, 음수 간선 및 사이클 처리 가능
SPFA	단일 시작점	✅ 가능	✅ 가능	평균 O(E), 최악 O(VE)	벨만-포드보다 빠름 (대부분 상황)
플로이드-워셜	모든 정점 쌍	✅ 가능	❌ (직접 탐지 X)	O(V³)	모든 거리 한 번에, 느림
Johnson	모든 정점 쌍	✅ 가능	❌ (존재하면 실패)	O(V² log V + VE)	희소 그래프에서 유리, 다익스트라 + 보정

어떤 걸 써야 할까?

상황	추천 알고리즘
시작점 하나, 양수 간선만	다익스트라
시작점 하나, 음수 간선 있음	벨만-포드 or SPFA
모든 정점 쌍, 정점 수 작음 (≤ 100)	플로이드-워셜
모든 정점 쌍, 정점 수 크고 희소 그래프	Johnson’s
음수 사이클 존재 여부 판단이 필요함	벨만-포드 or SPFA

✅ 4. 최소 신장 트리 (MST)

그래프에서 모든 정점을 연결하면서 전체 가중치의 합이 최소가 되는 트리를 찾는 알고리즘입니다.
사이클이 없고, 간선의 수가 정점 수 - 1개인 트리를 구성합니다.

1. 크루스칼 알고리즘 (Kruskal’s Algorithm)

간선을 가중치 순으로 정렬하고, 사이클이 생기지 않도록 하나씩 선택해 연결
Union-Find(Disjoint Set) 자료구조 활용

전략: 가중치가 가장 작은 간선부터 선택
간선을 정렬한 후 사이클이 생기지 않도록 연결
간선 중심 방식

시간 복잡도:

O(E log E) (간선 정렬 비용)

사용 예시:

  
def kruskal(n, edges):
    parent = [i for i in range(n + 1)]

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        a = find(a)
        b = find(b)
        if a != b:
            parent[b] = a
            return True
        return False

    edges.sort(key=lambda x: x[2])  # 가중치 기준 정렬
    total = 0
    for u, v, weight in edges:
        if union(u, v):
            total += weight
    return total

장점:

구현 간단, 간선 수가 많을 때 유리

단점:

정점 연결 상태를 확인하기 위해 유니온-파인드 구현 필요

2. 프림 알고리즘 (Prim’s Algorithm)

정점 하나에서 시작해, 연결된 정점 중 가장 가중치가 낮은 간선을 선택
우선순위 큐(heapq)로 구현

전략: 트리에 연결 가능한 가장 짧은 간선 선택
방문한 정점에서 확장하는 방식
정점 중심 방식

시간 복잡도:

O(E log V) (heapq 사용 시)

사용 예시:

  
import heapq

def prim(start, graph, n):
    visited = [False] * (n + 1)
    heap = [(0, start)]
    total = 0

    while heap:
        weight, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        total += weight
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (w, v))
    return total

장점:

구현이 직관적, 정점 수가 적고 간선이 많을 때 유리

단점:

간선이 희소한 그래프에서는 다소 느릴 수 있음

MST 알고리즘 비교 요약표

알고리즘	방식	자료구조	시간 복잡도	특징
크루스칼	간선 중심	유니온-파인드	O(E log E)	간선 위주, 정렬 필요
프림	정점 중심	우선순위 큐 (`heapq`)	O(E log V)	정점 확장 방식, 시작점 필요

어떤 걸 써야 할까?

상황	추천 알고리즘
간선이 많고 정점 수가 작음	크루스칼
정점 수가 많고 간선이 희소하지 않음	프림
모든 정점을 반드시 연결해야 함	둘 다 가능 (MST 문제임)

✅ 5. 그래프 연습 문제 추천

난이도	문제 링크
⭐⭐	백준 1753 - 최단경로 (다익스트라)
⭐⭐⭐	백준 1865 - 웜홀 (벨만포드)
⭐⭐⭐⭐	백준 1197 - 최소 스패닝 트리 (크루스칼)
⭐⭐⭐⭐	백준 11404 - 플로이드

✅ 6. 문제 풀이

백준 1753 - 최단경로 (다익스트라)

  
import sys
import heapq
input = sys.stdin.readline

v,e = map(int,input().split())
k = int(input())
g = {i+1:[] for i in range(v)}
for _ in range(e):
    a,b,w = map(int,input().split())
    g[a].append((b,w))
def dijkstra(s):
    d = [float('inf')] * (v+1)
    d[s] = 0
    heap = [(0,s)]
    while heap:
        dist,now =heapq.heappop(heap)
        if d[now] < dist:
            continue
        for b,w in g[now]:
            cost = dist + w
            if cost < d[b]:
                d[b] = cost
                heapq.heappush(heap,(cost,b))
    return d

d = dijkstra(k)
for i in d[1:]:
    print(i if i != float('inf') else 'INF')

heapq
Python 내장 우선순위 큐 (최소 힙)
항상 가장 작은 값이 먼저 나옴
push, pop → O(log N)
1 2 3 4 5 import heapq heap = [] heapq.heappush(heap, value) # 값 추가 heapq.heappop(heap) # 가장 작은 값 꺼내기 heapq.heapify(list) # 리스트를 힙 구조로 변환
다익스트라에서 왜 heapq를 쓸까?
다익스트라는 가장 가까운 정점을 반복적으로 찾아야 함
heapq를 사용하면 → 최소 거리 정점을 빠르게 꺼낼 수 있음
시간복잡도 개선: O(V²) → O(E log V)

백준 1865 - 웜홀 (벨만포드)

  
import sys
input = sys.stdin.readline

def bellman_ford(n,g):
    d = [0] * (n+1)
    
    for i in range(1,n):
        for u,v,w in g:
            if d[v] > d[u]+w:
                d[v] = d[u] +w
    for u,v,w in g:
        if d[v] > d[u]+w:
            return 'YES'
    return 'NO'

tc = int(input())
for _ in range(tc):
    n,m,w=map(int,input().split())
    g = []
    for _ in range(m):
        s,e,t = map(int,input().split())
        g.append((s,e,t))
        g.append((e,s,t))
    for _ in range(w):
        s,e,t = map(int,input().split())
        g.append((s,e,-t))
    print(bellman_ford(n,g))

백준 1197 - 최소 스패닝 트리 (크루스칼)

  
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
v,e = map(int,input().split())

p = [i for i in range(v+1)]
g = [list(map(int,input().split())) for _ in range(e)]
def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

def union(a,b):
    a = find(a)
    b = find(b)
    if a!=b:
        p[b] = a
        return True
    return False
cnt = 0
g.sort(key = lambda x : x[2])
for u, v, w in g:
    if union(u,v):
        cnt+=w
print(cnt)

백준 11404 - 플로이드

  
import sys
import heapq

input = sys.stdin.readline

n = int(input())
m = int(input())
answer = []
g = {i + 1: [] for i in range(n)}

for _ in range(m):
    a, b, c = map(int, input().split())
    found = False
    for idx, (nb, nc) in enumerate(g[a]):
        if nb == b:
            if c < nc:
                g[a][idx] = (b, c)
            found = True
            break
    if not found:
        g[a].append((b, c))

for i in range(1, n + 1):
    cost = [float('inf')] * (n + 1)
    heap = [(0, i)]
    cost[i] = 0

    while heap:
        now_cost, now = heapq.heappop(heap)
        if cost[now] < now_cost:
            continue
        for next_, c in g[now]:
            sum_ = now_cost + c
            if sum_ < cost[next_]:
                cost[next_] = sum_
                heapq.heappush(heap, (sum_, next_))

    for j in range(1, n + 1):
        if cost[j] == float('inf'):
            cost[j] = 0

    answer.append(cost)

for r in answer:
    print(' '.join(map(str, r[1:])))

이슈 1:

원인: 중복된 노드 중 낮은 값만 append하기

해결

  
for _ in range(m):
 a, b, c = map(int, input().split())
 found = False
 for idx, (nb, nc) in enumerate(g[a]):
     if nb == b:
         if c < nc:
             g[a][idx] = (b, c)
         found = True
         break
 if not found:
     g[a].append((b, c))

Algorithm, Graph

Algorithm Graph

This post is licensed under CC BY 4.0 by the author.

💾 그래프 (Graph)

✅ 1. 그래프란?

📌 그래프 용어 정리

✅ 2. 그래프의 표현 방식

2.1 인접 리스트 (Adjacency List)

2.2 인접 행렬 (Adjacency Matrix)

✅ 3. 최단 경로 알고리즘

1. 다익스트라 (Dijkstra)

2. 벨만-포드 (Bellman-Ford)

3. SPFA (Shortest Path Faster Algorithm)

4. 플로이드-워셜 (Floyd-Warshall)

5. Johnson’s Algorithm

알고리즘 비교 요약표

어떤 걸 써야 할까?

✅ 4. 최소 신장 트리 (MST)

1. 크루스칼 알고리즘 (Kruskal’s Algorithm)

2. 프림 알고리즘 (Prim’s Algorithm)

MST 알고리즘 비교 요약표

어떤 걸 써야 할까?

✅ 5. 그래프 연습 문제 추천

✅ 6. 문제 풀이

Trending Tags