06. Algorithm_Graphs (BFS, DFS, MST, Topological Sort, Shortest Paths)

학습 목표

• 그래프의 정의, 용어, 종류, 연결성
• 인접 행렬과 인접 리스트 표현
• BFS(큐)와 DFS(스택/재귀)의 동작과 \(\Theta(V + E)\)
• 최소 신장 트리: Prim과 Kruskal 알고리즘, \(O(E \log V)\)
• 위상 정렬 두 가지(진입 간선 제거, DFS 완료 역순)
• 최단 경로: Dijkstra, Bellman-Ford, DAG 최단 경로와 음의 가중치 문제

---

1. 그래프 기본

• 그래프 \(G = (V, E)\): 정점(vertex)의 집합 V와, 두 정점을 잇는 간선(edge)의 집합 E
• 간선의 길이나 정점의 위치는 중요하지 않고, 어떤 정점들이 연결되어 있는지만 중요함
• 두 정점이 간선으로 연결되어 있으면 인접(adjacent) 하다고 함. 한 정점에 붙은 간선의 수가 그 정점의 차수(degree)

용어	뜻
경로 (path)	간선으로 이어진 정점들의 나열. 경로의 길이는 지나는 간선 수
단순 경로	같은 정점을 두 번 지나지 않는 경로
사이클	시작 정점으로 돌아오는 경로
단순 사이클	시작 정점을 빼면 같은 정점을 두 번 지나지 않는 사이클

종류	설명
완전 그래프	모든 정점 쌍이 간선으로 연결
정규 그래프	모든 정점의 차수가 같음
순환 그래프	정점들이 하나의 고리로 이어진 그래프 (모든 정점의 차수가 2인 정규 그래프)
트리	사이클이 없는 연결 그래프
이분 그래프	정점을 두 색으로 칠할 때 모든 간선의 양 끝이 서로 다른 색
평면 그래프	간선끼리 정점 이외의 곳에서 만나지 않게 그릴 수 있음

• 연결 그래프: 모든 정점 쌍 사이에 경로가 있음. 비연결 그래프: 경로가 없는 정점 쌍이 하나라도 있음

표현 방법

구분	인접 행렬	인접 리스트
구조	\(N \times N\) 행렬, \((i, j)\)가 1(또는 가중치)이면 간선 있음	정점마다 인접한 정점(과 가중치)의 연결 리스트
공간	\(\Theta(V^2)\)	\(\Theta(V + E)\)
두 정점이 인접한지 확인	\(O(1)\)	리스트 길이만큼
알맞은 그래프	간선이 많은(조밀한) 그래프	간선이 적은(희소한) 그래프

무향 그래프의 인접 행렬은 대칭 행렬, 유향 그래프는 일반적으로 비대칭.

---

2. 그래프 탐색

구분	BFS (너비 우선)	DFS (깊이 우선)
방식	시작점에서 가까운 정점부터 층별로 넓게	한 방향으로 갈 수 있는 데까지 깊게 들어갔다가 되돌아옴
자료구조	큐	스택 (또는 재귀)
용도	간선 수 기준 최단 경로	모든 정점 방문, 경로 찾기, 위상 정렬
수행 시간	\(\Theta(V + E)\)	\(\Theta(V + E)\)

모든 정점과 간선을 한 번씩만 확인하므로 둘 다 \(\Theta(V + E)\) (인접 리스트 기준).

---

3. 최소 신장 트리 (MST)

• 트리: 사이클이 없는 연결 그래프. 정점이 n개면 간선은 항상 \(n - 1\)개
• 신장 트리: 그래프 G의 모든 정점을 포함하고 G의 간선만으로 만든 트리 (BFS, DFS 트리도 신장 트리)
• 최소 신장 트리: 신장 트리 중 간선 가중치의 합이 최소인 것. 무향 연결 그래프에서 정의됨

알고리즘	방법	수행 시간
Prim	정점 하나에서 시작한 집합 S를 키움. 매번 S 안과 밖을 잇는 간선 중 가장 싼 것을 추가	최소 힙 사용 시 \(O(E \log V)\)
Kruskal	모든 간선을 가중치 순으로 보며, 사이클을 만들지 않으면 추가. 여러 트리가 동시에 자라다 합쳐짐	정렬 \(O(E \log E) = O(E \log V)\), Union-Find로 사이클 검사

둘 다 매 순간 가장 좋아 보이는 선택을 하는 그리디 알고리즘이지만, MST에서는 최적해가 보장됨 (07편의 매트로이드).

---

4. 위상 정렬

사이클이 없는 유향 그래프(DAG) 의 정점들을, 간선 \(x \to y\)가 있으면 x가 y보다 앞에 오도록 일렬로 나열하는 것. 작업들 사이에 선행 관계가 있을 때의 작업 순서. 답이 여러 개일 수 있음.

알고리즘	방법	수행 시간
TSA1	진입 간선이 없는 정점을 하나 골라 결과에 추가하고, 그 정점과 나가는 간선을 지움. 반복 (큐)	\(O(V + E)\)
TSA2	DFS를 하면서 탐색이 끝난(완료된) 정점을 연결 리스트 맨 앞에 추가 → 완료 순서의 역순	\(O(V + E)\)

TSA2에서 가장 먼저 완료되는 정점은 더 갈 곳이 없는 마지막 작업이므로, 맨 앞에 계속 끼워 넣으면 결국 맨 앞에는 가장 먼저 시작해야 할 작업이 옴.

---

5. 최단 경로

간선에 가중치가 있는 유향 그래프에서 두 정점 사이의 가중치 합이 최소인 경로. 무향 그래프는 간선마다 양방향 간선이 있는 것으로 봄.

유형	알고리즘	조건	수행 시간
단일 시작점	Dijkstra	음의 가중치 불허	\(O(E \log V)\) (힙)
단일 시작점	Bellman-Ford	음의 가중치 허용, 음의 사이클은 검출	\(O(VE)\)
단일 시작점	DAG 최단 경로	사이클 없는 그래프, 음의 가중치 허용	\(O(V + E)\)
모든 쌍	Floyd-Warshall	음의 사이클 없음	\(O(V^3)\)

Dijkstra

• 거리가 확정된 정점 집합 S를 키움. 매번 S 밖에서 시작점으로부터 거리가 가장 짧은 정점을 S에 넣고, 그 정점에서 나가는 간선으로 이웃의 거리를 이완(relaxation)
• Prim과 비교 (출제!!): 구조는 거의 같지만 v.dist의 의미가 다름

구분	Prim	Dijkstra
목적	모든 정점을 최소 비용으로 연결 (MST)	시작점에서 각 정점까지의 최단 경로
v.dist의 뜻	v를 현재 트리에 연결하는 간선 하나의 최소 비용	시작점에서 v까지 경로의 누적 최소 비용

• 음의 가중치를 허용하지 않는 이유: S에 들어간 정점은 거리가 확정되었다고 보고 다시 갱신하지 않음. 음의 간선이 있으면 나중에 S 밖의 정점을 거쳐 더 짧은 경로가 생겨도 반영되지 않아 틀린 답이 나옴

Bellman-Ford

• 모든 간선을 이완하는 일을 \(V - 1\)번 반복
• 왜 \(V - 1\)번인가: 정점이 V개면 가장 긴 단순 경로의 간선 수는 \(V - 1\)개. i번째 반복이 끝나면 간선 i개 이하로 갈 수 있는 최단 거리가 모두 구해짐
• \(V\)번째 반복에서도 거리가 줄어들면 음의 사이클이 있다는 뜻 (돌수록 거리가 무한히 줄어들어 최단 경로가 정의되지 않음)

DAG 최단 경로

정점을 위상 정렬 순서대로 처리하며 나가는 간선을 이완. 어떤 정점을 처리할 때 그 정점으로 들어오는 경로는 이미 모두 처리되었으므로 한 번에 끝남.

---

6. 예제로 실행하기

무향 가중 그래프로 BFS, DFS, Prim, Kruskal을, “라면 끓이기” DAG로 위상 정렬을, 여러 유향 그래프로 최단 경로를 실행하고 networkx 결과와 비교함.

import heapq
from collections import deque

# 무향 가중 그래프 (MST, BFS, DFS용)
UND = {"a": {"b": 8, "c": 11, "d": 9}, "b": {"a": 8, "e": 10}, "c": {"a": 11, "d": 13, "f": 8},
       "d": {"a": 9, "c": 13, "e": 5, "g": 12}, "e": {"b": 10, "d": 5, "h": 8},
       "f": {"c": 8, "g": 7}, "g": {"d": 12, "f": 7, "h": 9}, "h": {"e": 8, "g": 9}}

def bfs(g, s):
    order, seen, q = [], {s}, deque([s])
    while q:
        u = q.popleft(); order.append(u)
        for v in sorted(g[u]):
            if v not in seen: seen.add(v); q.append(v)
    return order

def dfs(g, s, seen=None, order=None):
    seen, order = seen or set(), order if order is not None else []
    seen.add(s); order.append(s)
    for v in sorted(g[s]):
        if v not in seen: dfs(g, v, seen, order)
    return order

def prim(g, r):
    """집합 S를 키워 가며, S와 바깥을 잇는 가장 싼 간선을 하나씩 추가"""
    in_s, edges, pq = {r}, [], [(w, r, v) for v, w in g[r].items()]
    heapq.heapify(pq)
    while pq and len(in_s) < len(g):
        w, u, v = heapq.heappop(pq)
        if v in in_s: continue
        in_s.add(v); edges.append((u, v, w))
        for x, wx in g[v].items():
            if x not in in_s: heapq.heappush(pq, (wx, v, x))
    return edges

def kruskal(g):
    """가중치 순으로 간선을 보며, 사이클을 만들지 않으면 추가 (Union-Find)"""
    parent = {v: v for v in g}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]       # 경로 압축
        return x
    edges = sorted((w, u, v) for u in g for v, w in g[u].items() if u < v)
    mst = []
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv; mst.append((u, v, w))
    return mst

print("BFS:", " ".join(bfs(UND, "a")))
print("DFS:", " ".join(dfs(UND, "a")))
p, k = prim(UND, "a"), kruskal(UND)
print("Prim    :", p, "합", sum(w for *_, w in p))
print("Kruskal :", k, "합", sum(w for *_, w in k))

# 유향 비순환 그래프 (위상 정렬, DAG 최단 경로)
DAG = {"냄비에 물 붓기": ["점화"], "라면 봉지 뜯기": ["라면 넣기", "수프 넣기"], "점화": ["라면 넣기", "수프 넣기"],
       "라면 넣기": ["달걀 풀기"], "수프 넣기": ["달걀 풀기"], "달걀 풀기": []}

def tsa1(g):                         # 진입 간선이 없는 정점을 하나씩 꺼내고 그 정점의 간선을 제거 (큐)
    indeg = {v: 0 for v in g}
    for u in g:
        for v in g[u]: indeg[v] += 1
    q, out = deque(v for v in g if indeg[v] == 0), []
    while q:
        u = q.popleft(); out.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return out

def tsa2(g):                         # DFS가 끝난 정점을 연결 리스트 맨 앞에 추가 (완료 순서의 역순)
    seen, out = set(), deque()
    def visit(u):
        seen.add(u)
        for v in g[u]:
            if v not in seen: visit(v)
        out.appendleft(u)
    for u in g:
        if u not in seen: visit(u)
    return list(out)

print("\n위상 정렬 TSA1:", " → ".join(tsa1(DAG)))
print("위상 정렬 TSA2:", " → ".join(tsa2(DAG)))

# 최단 경로
def dijkstra(g, s):
    d = {v: float("inf") for v in g}; d[s] = 0
    S, pq = set(), [(0, s)]
    while pq:
        du, u = heapq.heappop(pq)
        if u in S: continue
        S.add(u)                                 # u의 거리는 이제 확정
        for v, w in g[u].items():
            if v not in S and du + w < d[v]:     # 확정된 정점은 다시 갱신하지 않음
                d[v] = du + w; heapq.heappush(pq, (d[v], v))
    return d

def bellman_ford(g, s):
    d = {v: float("inf") for v in g}; d[s] = 0
    edges = [(u, v, w) for u in g for v, w in g[u].items()]
    for _ in range(len(g) - 1):                  # 간선 n-1개짜리 경로까지 고려
        for u, v, w in edges:
            if d[u] + w < d[v]: d[v] = d[u] + w
    neg_cycle = any(d[u] + w < d[v] for u, v, w in edges)   # n번째에도 줄면 음의 사이클
    return d, neg_cycle

def dag_shortest(g, s):
    d = {v: float("inf") for v in g}; d[s] = 0
    for u in tsa2(g):                            # 위상 정렬 순서대로 이완
        for v, w in g[u].items():
            if d[u] + w < d[v]: d[v] = d[u] + w
    return d

POS = {"s": {"a": 10, "b": 5}, "a": {"c": 1, "b": 2}, "b": {"a": 3, "c": 9, "d": 2},
       "c": {"d": 4}, "d": {"s": 7, "c": 6}}
print("\n양수 가중치 그래프")
print("  Dijkstra    :", dijkstra(POS, "s"))
print("  Bellman-Ford:", bellman_ford(POS, "s"))

NEG = {"s": {"a": 2, "b": 4}, "a": {"c": 3}, "b": {"a": -3}, "c": {}}
print("\n음의 가중치 간선 b→a = -3")
print("  Dijkstra    :", dijkstra(NEG, "s"), "← a가 먼저 확정되어 s→b→a(1)를 놓침")
print("  Bellman-Ford:", bellman_ford(NEG, "s"))

CYC = {"s": {"a": 1}, "a": {"b": 1}, "b": {"a": -3}}
print("\n음의 사이클 a→b→a (합 -2)")
print("  Bellman-Ford:", bellman_ford(CYC, "s"), "← True면 음의 사이클 존재")

WDAG = {"r": {"s": 5, "t": 3}, "s": {"t": 2, "x": 6}, "t": {"x": 7, "y": 4, "z": 2},
        "x": {"y": -1, "z": 1}, "y": {"z": -2}, "z": {}}
print("\nDAG 최단 경로 (음의 간선 있음):", dag_shortest(WDAG, "s"))
print("  Bellman-Ford와 같은가:", dag_shortest(WDAG, "s") == bellman_ford(WDAG, "s")[0])

# networkx로 교차 검증
import networkx as nx
G = nx.Graph([(u, v, {"weight": w}) for u in UND for v, w in UND[u].items()])
D = nx.DiGraph([(u, v, {"weight": w}) for u in POS for v, w in POS[u].items()])
print("\nnetworkx MST 가중치 합:", int(nx.minimum_spanning_tree(G).size(weight="weight")),
      "/ 최단 거리 일치:", dict(nx.single_source_dijkstra_path_length(D, "s")) == dijkstra(POS, "s"))

실행 결과

BFS: a b c d e f g h
DFS: a b e d c f g h
Prim    : [('a', 'b', 8), ('a', 'd', 9), ('d', 'e', 5), ('e', 'h', 8), ('h', 'g', 9), ('g', 'f', 7), ('f', 'c', 8)] 합 54
Kruskal : [('d', 'e', 5), ('f', 'g', 7), ('a', 'b', 8), ('c', 'f', 8), ('e', 'h', 8), ('a', 'd', 9), ('g', 'h', 9)] 합 54

위상 정렬 TSA1: 냄비에 물 붓기 → 라면 봉지 뜯기 → 점화 → 라면 넣기 → 수프 넣기 → 달걀 풀기
위상 정렬 TSA2: 라면 봉지 뜯기 → 냄비에 물 붓기 → 점화 → 수프 넣기 → 라면 넣기 → 달걀 풀기

양수 가중치 그래프
  Dijkstra    : {'s': 0, 'a': 8, 'b': 5, 'c': 9, 'd': 7}
  Bellman-Ford: ({'s': 0, 'a': 8, 'b': 5, 'c': 9, 'd': 7}, False)

음의 가중치 간선 b→a = -3
  Dijkstra    : {'s': 0, 'a': 2, 'b': 4, 'c': 5} ← a가 먼저 확정되어 s→b→a(1)를 놓침
  Bellman-Ford: ({'s': 0, 'a': 1, 'b': 4, 'c': 4}, False)

음의 사이클 a→b→a (합 -2)
  Bellman-Ford: ({'s': 0, 'a': -3, 'b': 0}, True) ← True면 음의 사이클 존재

DAG 최단 경로 (음의 간선 있음): {'r': inf, 's': 0, 't': 2, 'x': 6, 'y': 5, 'z': 3}
  Bellman-Ford와 같은가: True

networkx MST 가중치 합: 54 / 최단 거리 일치: True

• Prim과 Kruskal이 고른 간선 순서는 다르지만 같은 MST(합 54)를 만들고, networkx의 결과와도 같음
• 위상 정렬 결과는 두 방법이 다르지만, 둘 다 모든 선행 관계를 지킴 (위상 정렬의 답은 여러 개일 수 있음)
• 음의 간선 b→a = -3이 있으면 Dijkstra는 a를 먼저 확정해 버려서 a까지 2로 답하지만, 실제 최단 거리는 s→b→a = 4 - 3 = 1. Bellman-Ford는 맞게 구함
• 음의 사이클이 있으면 Bellman-Ford가 이를 검출함 (True)
• DAG 최단 경로는 음의 간선이 있어도 위상 순서 한 번으로 Bellman-Ford와 같은 답을 냄

강의 코드 실행

강의록의 01_dijkstra.py, 02_bellman_ford.py는 무작위 그래프를 만드는 클래스라서, 시드를 고정하고 그대로 불러와 실행함 (그림 저장 부분은 networkx와 matplotlib를 씀).

import random, importlib, sys
sys.path.insert(0, ".")
Dijkstra = importlib.import_module("01_dijkstra").Dijkstra          # 강의 코드 그대로 불러오기
BellmanFord = importlib.import_module("02_bellman_ford").BellmanFord

random.seed(1)                                                      # 그래프가 매번 바뀌지 않게 시드 고정
g = Dijkstra(num_nodes=6, edge_prob=0.4)
g.print_graph(); g.dijkstra(start=0); g.print_shortest_paths(start=0)
g.visualize(start=0, filename="dijkstra.png")

random.seed(7)
bf = BellmanFord(num_nodes=6, edge_prob=0.5, weight_range=(-5, 10), negative_edge_ratio=0.05)
bf.print_graph()
if bf.bellman_ford(start=0):
    bf.print_shortest_paths(start=0); bf.visualize(start=0, filename="bellman_ford.png")
else:
    print("음수 사이클이 존재하여 최단 경로를 계산할 수 없습니다.")

실행 결과

입력 그래프 (인접 리스트):
정점 0 → 1(가중치=2), 2(가중치=8), 5(가중치=4)
정점 1 → 0(가중치=1), 3(가중치=10), 5(가중치=8)
정점 2 → 0(가중치=4), 3(가중치=6), 4(가중치=1)
정점 3 → 0(가중치=7)
정점 4 → 3(가중치=4)
정점 5 → 


시작 정점: 0

정점 0까지의 최단 거리: 0
경로: 0

정점 1까지의 최단 거리: 2
경로: 0 → 1

정점 2까지의 최단 거리: 8
경로: 0 → 2

정점 3까지의 최단 거리: 12
경로: 0 → 1 → 3

정점 4까지의 최단 거리: 9
경로: 0 → 2 → 4

정점 5까지의 최단 거리: 4
경로: 0 → 5

✅ 그래프가 'dijkstra.png' 파일로 저장되었습니다.
입력 그래프 (간선 리스트):
정점  0 →  1 (가중치=-1)
정점  0 →  2 (가중치= 2)
정점  0 →  4 (가중치= 9)
정점  0 →  5 (가중치= 7)
정점  1 →  0 (가중치= 2)
정점  1 →  2 (가중치= 8)
정점  1 →  3 (가중치= 4)
정점  2 →  0 (가중치= 7)
정점  2 →  1 (가중치= 2)
정점  2 →  3 (가중치= 5)
정점  2 →  4 (가중치=10)
정점  3 →  0 (가중치= 1)
정점  3 →  1 (가중치=10)
정점  3 →  2 (가중치= 1)
정점  3 →  4 (가중치= 8)
정점  4 →  0 (가중치= 9)
정점  4 →  1 (가중치= 2)
정점  4 →  5 (가중치= 4)
정점  5 →  3 (가중치= 2)


시작 정점: 0

정점 0까지의 최단 거리: 0
경로: 0

정점 1까지의 최단 거리: -1
경로: 0 → 1

정점 2까지의 최단 거리: 2
경로: 0 → 2

정점 3까지의 최단 거리: 3
경로: 0 → 1 → 3

정점 4까지의 최단 거리: 9
경로: 0 → 4

정점 5까지의 최단 거리: 7
경로: 0 → 5

✅ 그래프가 'bellman_ford.png' 파일로 저장되었습니다.

• Dijkstra 결과에서 정점 3은 0→1→3(2 + 10 = 12)이 0→2→4→3(8 + 1 + 4 = 13)보다 짧음
• Bellman-Ford 그래프에는 음의 간선 0→1(-1)이 있고, 정점 3은 0→1→3(-1 + 4 = 3)이 최단

---

정리 노트에서 정정한 부분 정리

위치	원래	정정	이유
그래프 정의	E: 간선 집합 == 차수	E는 간선 집합. 차수는 한 정점에 붙은 간선 수	서로 다른 개념
용어	경로: 연결된 간선들의 개수	경로는 간선으로 이어진 정점의 나열이고, 간선 수는 경로의 길이	정의와 길이 구분
용어	단순 사이클: 사이클을 포함하지 않는 사이클	시작 정점 외에 같은 정점을 반복하지 않는 사이클	자기모순적인 정의
연결성	비연결: 모든 정점 간에 경로가 존재하지 않음	경로가 없는 정점 쌍이 하나라도 있음	일부만 끊겨도 비연결
그래프 종류	순환 그래프: 모든 꼭짓점이 같은 차수	하나의 고리 모양(모든 정점 차수 2)	같은 차수는 정규 그래프의 정의
최단 경로 조건	가중치의 값이 음수는 허용하지 않는다	Dijkstra만 음수 불허. Bellman-Ford, DAG 최단 경로는 음의 간선 허용	음의 사이클이 없으면 최단 경로가 정의됨
Bellman-Ford	음의 사이클을 허용하지 않음	음의 사이클이 있으면 검출해서 알려 줌	V번째 반복에서 거리가 줄면 사이클 존재

---

최종 핵심 정리

1. 그래프는 \(G = (V, E)\)이고, 희소 그래프는 인접 리스트(\(\Theta(V+E)\) 공간), 조밀 그래프는 인접 행렬(\(\Theta(V^2)\))이 알맞음
2. BFS는 큐로 가까운 정점부터, DFS는 스택(재귀)으로 깊게 탐색하며 둘 다 \(\Theta(V + E)\)
3. MST는 간선 합이 최소인 신장 트리이고, n개 정점이면 간선 \(n - 1\)개
4. Prim은 집합 S를 키우며 S 경계의 최소 간선을, Kruskal은 사이클을 만들지 않는 최소 간선을 추가하며 둘 다 \(O(E \log V)\)
5. 위상 정렬은 DAG에서 선행 관계를 지키는 나열이며, 진입 간선 제거(TSA1)나 DFS 완료 역순(TSA2)으로 \(O(V + E)\)
6. Dijkstra는 음의 간선이 없을 때 \(O(E \log V)\)이고, 확정한 정점을 다시 갱신하지 않아 음의 간선이 있으면 틀림
7. Bellman-Ford는 모든 간선 이완을 \(V - 1\)번 반복해 음의 간선을 처리하고 음의 사이클을 검출하며 \(O(VE)\)
8. DAG에서는 위상 정렬 순서대로 한 번 이완하면 \(O(V + E)\)에 최단 경로를 구함

---

End.