0x07. 기본 그래프 알고리즘

그래프의 기본 개념

그래프는 정점(Vertex) 의 집합과 간선(Edge) 의 집합으로 이루어진 자료구조다. 네트워크 경로, 의존 관계, 소셜 관계 등 현실 세계의 다양한 관계를 모델링할 수 있어 컴퓨터 과학 전반에서 핵심적인 역할을 한다.

그래프의 종류

그래프는 크게 두 가지 기준으로 분류된다.

가중치 여부: 간선에 가중치가 있는 가중 그래프(Weighted Graph) 와 가중치가 없는 비가중 그래프(Unweighted Graph) 로 나뉜다.

방향 여부:

방향 그래프(Directed Graph, Digraph): 간선에 방향이 있다. 간선 (u, v)에서 u는 head, v는 tail이다.
무방향 그래프(Undirected Graph): 간선에 방향이 없다. 일반적으로 자기 자신으로의 간선(self-loop)은 허용되지 않으며, 동일한 간선이 중복될 수 없다.

대칭 방향 그래프(Symmetric Digraph) 는 모든 간선 vw에 대해 역방향 간선 wv도 함께 존재하는 특수한 방향 그래프다.

완전 그래프(Complete Graph) 는 모든 정점 쌍 사이에 간선이 존재하는 무방향 그래프다.

그래프의 크기

그래프의 크기는 두 가지 값으로 표현된다.

n: 정점(노드)의 수
m: 간선의 수

밀집 그래프(Dense Graph) 는 간선이 많은 그래프다.

무방향: 모든 정점이 서로 연결되면 m = n(n-1)/2 로, 이것이 완전 그래프다.
방향: m = n(n-1)

희소 그래프(Sparse Graph) 는 간선이 적은 그래프다. 극단적으로 간선이 0개일 수도 있다.

경로, 사이클, 부분 그래프

경로(Path) 는 정점의 나열 P = (v $_0$ , v $_1$ , ..., v $_k$ )으로, 1 ≤ i ≤ k인 모든 i에 대해 간선 (v $_{i-1}$ , v $_i$ ) ∈ E를 만족한다. 어떤 정점도 두 번 이상 등장하지 않으면 단순 경로(Simple Path) 라 한다.

사이클(Cycle) 은 정점의 나열 C = (v $_0$ , v $_1$ , ..., v $_{k-1}$ )로, 0 ≤ i < k인 모든 i에 대해 간선 (v $_i$ , v $_{(i+1) \mod k}$ ) ∈ E를 만족한다. 내부 경로 (v $_0$ , v $_1$ , ..., v $_{k-1}$ )가 단순 경로이면 단순 사이클이라 한다.

그래프 H = (W, F)가 그래프 G = (V, E)의 부분 그래프(Subgraph) 이려면 W ⊆ V 이고 F ⊆ E여야 한다. 신장 그래프(Spanning Graph) 는 G의 모든 정점을 포함하는 부분 그래프다.

연결성

무방향 그래프의 연결성:

연결 그래프(Connected Graph): 임의의 두 정점 사이에 경로가 존재하는 그래프다.
연결 요소(Connected Component): 극대(maximal) 연결 부분 그래프다.

방향 그래프의 강연결(Strongly Connected):

방향 그래프에서는 방향이 연결성에 영향을 준다. 정점 u에서 v로 도달 가능하더라도 v에서 u로 도달 가능하지 않을 수 있다.
강연결이란 양방향 모두 도달 가능한 상태, 즉 대칭적인 도달 가능성을 의미한다.

특수한 그래프 구조

비순환 그래프(Acyclic Graph): 사이클이 없는 그래프
DAG(Directed Acyclic Graph): 사이클이 없는 방향 그래프. 위상 정렬 등 다양한 응용에 활용된다.
트리(Tree): 연결이면서 사이클이 없는 그래프
신장 트리(Spanning Tree): 신장 그래프이면서 트리인 그래프

그래프의 표현

그래프를 컴퓨터에 저장하는 대표적인 방법은 두 가지다.

인접 행렬(Adjacency Matrix) -- O(V $^2$ ) 저장 공간

정점이 4개인 무방향 그래프를 인접 행렬로 표현할 때 최소 저장 공간은 6 bits다. 무방향 그래프의 인접 행렬은 대칭이므로 절반만 저장하면 되고, 자기 루프가 없으므로 대각선도 필요 없다.

인접 행렬은 밀집 그래프에 적합하다. 큰 그래프에서는 저장 공간이 과도하지만, 작은 그래프에서는 매우 효율적일 수 있다. 대부분의 대규모 그래프는 희소 그래프이므로, 이런 경우에는 인접 리스트가 더 적절한 표현 방식이다.

인접 리스트(Adjacency List) -- O(V+E) 저장 공간

BFS (너비 우선 탐색)

BFS(Breadth-First Search)는 그래프를 스캔하여 너비 우선 신장 트리(Breadth-First Spanning Tree) 를 구축하는 알고리즘이다. 마치 호수에 돌을 던졌을 때 파문이 퍼져 나가는 것처럼, 시작 정점에서 가까운 정점부터 차례로 방문한다.

동작 원리

시작 정점 s를 루트로 선택한다.
s의 인접 정점(자식)을 발견하고, 그 다음에는 그들의 인접 정점을 발견하는 식으로 확장해 나간다.
s에서 도달 가능한 모든 정점 v에 대해, 트리에서 s에서 v까지의 경로는 G에서의 최단 경로에 해당한다.

여기서 두 가지 핵심 용어를 구분해야 한다.

Discover(발견): 정점을 처음 만나는 것. 모든 도달 가능한 정점이 발견된다.
Explore(탐색): 간선을 처음 조사하는 것. 탐색되지 않는 간선이 존재할 수 있다.

색상 기반 상태 관리

BFS는 각 정점을 세 가지 색으로 관리한다.

White(흰색): 아직 발견되지 않은 상태. 모든 정점은 처음에 흰색이다.
Gray(회색): 발견되었지만 아직 처리가 끝나지 않은 상태. 흰색 정점과 인접해 있을 수 있으며, 너비 우선 트리에 추가된다.
Black(검정): 발견되었고 처리가 완료된 상태. 검정 또는 회색 정점하고만 인접한다.

흰색 정점이 발견되면 회색으로 바꾸고, 그 정점의 모든 흰색 이웃을 발견한다. 모든 이웃이 발견되면 검정으로 바꾸어 완료 표시를 한다. 회색 정점의 인접 리스트를 스캔하며 새로운 정점을 발견해 나간다.

시간 복잡도 분석

BFS의 수행 시간은 다음과 같이 분석된다.

A. 각 노드는 한 번만 큐에 삽입된다 (white → gray): $\Theta$ (V)
B. 각 노드는 한 번만 큐에서 제거된다 (gray → black): $\Theta$ (V)
C. 각 인접 리스트는 한 번만 스캔된다: $\Theta$ (E)

따라서 전체 수행 시간은 $\Theta$ (V+E) 이다.

비유: 섬과 다리

정점을 섬, 간선을 다리라고 생각해 보자. BFS는 여러 사람이 출발점에서 동시에(또는 거의 동시에) 각 방향으로 퍼져 나가며 탐색하는 것과 같다.

연습 문제

위 그래프에서 정점 'a'를 루트로 하여 너비 우선 신장 트리를 만들어 보자. 정점은 알파벳 순서로, 각 인접 리스트도 알파벳 순서로 정렬되어 있다고 가정한다.

정점 c에서 루트까지의 최소 거리는 3이다.

BFS의 성질

정리 1: BFS는 루트로부터의 거리가 증가하는 순서로 정점을 방문한다. BFS가 만든 너비 우선 트리에서 루트까지의 경로는 원래 그래프 G에서의 최단 경로를 나타낸다.

정리 2: 그래프 G의 모든 간선 (v, w)에 대해 v ∈ L $_i$ 이고 w ∈ L $_j$ 이면, |i - j| ≤ 1 이다. 즉, 인접 정점은 같은 레벨이거나 한 레벨 차이가 난다.