그래프 탐색, 최단경로와 최소신장트리

핵심 요약

BFS·DFS·위상정렬·최단경로·최소신장트리 알고리즘의 적용 조건을 구분한다.

본문

BFS와 DFS

BFS

시작 정점에서 가까운 정점부터 레벨 순서로 방문하며 큐를 사용한다. 가중치가 없거나 모든 간선 가중치가 같은 그래프의 최단 간선 수를 구할 수 있다.

• 인접리스트 기준 O(V+E)
• 최단 거리, 연결 요소, 이분 그래프 판정 등에 사용

DFS

한 경로를 가능한 깊게 탐색한 뒤 되돌아오며 재귀 또는 스택을 사용한다.

• 인접리스트 기준 O(V+E)
• 사이클 판정, 위상정렬, 경로 탐색, 연결 요소 등에 사용

방문 순서는 인접 정점의 저장 순서에 따라 달라질 수 있으므로 문제에서 “작은 번호부터” 같은 조건을 확인해야 한다.

위상정렬

방향 비순환 그래프(DAG)의 정점을 모든 간선 방향을 지키도록 일렬로 나열한다.

• 진입차수가 0인 정점을 큐에서 꺼내는 Kahn 방식
• DFS 종료 순서의 역순을 사용하는 방식
• 사이클이 있으면 모든 정점을 위상정렬할 수 없다.
• 결과가 하나로 유일하지 않을 수 있다.

최단경로

* 음수 사이클이 없어야 정상적인 최단거리가 정의된다.

완화(relaxation)는 dist[v] > dist[u] + w(u,v)이면 더 짧은 값으로 갱신하는 연산이다.

최소신장트리(MST)

연결된 가중 무방향 그래프의 모든 정점을 연결하면서 간선 가중치 합이 최소인 트리이다. 정점이 V개이면 간선은 V-1개이다.

Kruskal

간선을 가중치 순으로 정렬하고 사이클을 만들지 않는 간선을 선택한다. 사이클 여부는 Union-Find로 효율적으로 확인한다.

Prim

하나의 정점에서 시작해 현재 트리와 외부 정점을 연결하는 가장 작은 간선을 반복 선택한다. 우선순위 큐를 사용할 수 있다.

Union-Find

서로소 집합을 관리한다.

• find(x): x가 속한 집합의 대표를 찾는다.
• union(a,b): 두 집합을 합친다.
• 경로 압축과 랭크·크기 기준 합치기로 성능을 높인다.

BFS·DFS 의사코드와 방문 시점

BFS는 큐에 넣는 순간 방문 표시를 해야 같은 정점이 여러 번 큐에 들어가는 것을 막는다.

from collections import deque
q = deque([start])
visited[start] = True
while q:
    u = q.popleft()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            dist[v] = dist[u] + 1
            q.append(v)

DFS는 재귀 진입 시 방문 표시한다. 재귀 스택의 색을 구분하면 방향 그래프의 back edge와 사이클을 판정할 수 있다.

위상정렬 추적

Kahn 방식은 진입차수 0인 정점을 큐에 넣고 제거하면서 이웃 진입차수를 줄인다.

A → C ← B, C → D
초기 진입차수 0: A, B
가능한 순서: A,B,C,D 또는 B,A,C,D

처리한 정점 수가 V보다 작으면 사이클이 존재한다. 큐에서 어떤 정점을 먼저 꺼내는지에 따라 여러 결과가 나올 수 있다.

Dijkstra와 완화

pq = [(0, s)]
while pq:
    d, u = heappop(pq)
    if d != dist[u]:
        continue
    for v, w in adj[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            heappush(pq, (nd, v))

우선순위 큐 구현은 보통 O((V+E) log V)이다. 음수 간선이 있으면 한 번 확정한 정점의 거리가 나중에 더 작아질 수 있어 탐욕적 확정이 안전하지 않다.

Bellman-Ford와 Floyd-Warshall

Bellman-Ford는 모든 간선을 V-1회 완화한다. 그 뒤 한 번 더 완화가 가능하면 시작점에서 도달 가능한 음수 사이클이 있다.

Floyd-Warshall의 상태는 “1..k번 정점만 중간 정점으로 허용했을 때 i에서 j까지 거리”이다.

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

시간 O(V³), 공간 O(V²)이며 모든 쌍 최단경로에 적합하다.

MST 선택 과정

Kruskal은 간선 중심, Prim은 정점 집합 확장 중심이다.

Kruskal: 간선 정렬→작은 간선부터 → 서로 다른 집합이면 채택Prim: 임의 시작→현재 트리에서 밖으로 나가는 최소 간선 채택

MST는 모든 정점을 최소 총비용으로 연결한다. 특정 시작점에서 각 정점까지 거리를 최소화하는 최단경로 트리와 목적이 다르다.

Union-Find 최적화

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

경로 압축과 랭크/크기 합치기를 함께 쓰면 연산의 분할 상환 비용은 거의 상수인 O(α(n))이다.

알고리즘 선택표

대표 알고리즘 선택 장면

도로 가중치가 모두 음수가 아니고 한 출발점에서 최단거리를 구하면 Dijkstra를 검토할 수 있다. 음수 간선이 있으면 선택 확정 규칙이 깨질 수 있어 다른 알고리즘이 필요하다. 모든 정점을 최소 총비용으로 잇는 MST는 두 정점 사이 최단경로 집합과 목적이 다르다.