그래프 알고리즘Graph Algorithms
정점과 간선으로 적은 연결 구조 위에서 «다 닿는가 · 한 출발점에서 가장 싼 길은 · 모두를 가장 싸게 잇는 법은»을 푸는 탐색 · 최단 경로 · 최소 신장 트리를 묶은 것이다. 간선을 가중치 순으로 늘어놓는 정렬을 비교 기준 알고리즘으로 함께 다루고, 그래프를 적는 자료 구조 자체는 자료구조가 맡는다.
1요약
- 그래프 알고리즘은 알고리즘 가운데 연결 구조 위의 세 질문(다 닿는가 · 가장 싼 길 · 가장 싼 연결)을 맡는 길목으로, 1956 ~ 1959년 최소 신장 트리(Kruskal 1956 · Prim 1957)와 최단 경로(Bellman 1958 · Dijkstra 1959)가 차례로 정리됐고 지금은 라우팅 · 지도 길찾기 · 배선 설계가 이 절차 위에서 돈다.
- 질문과 절차를 어긋나게 고르면 답이 틀리거나 비용이 폭발한다 — 사례 그래프에서 간선 수가 가장 적은 길은 비용 10, 가장 싼 길은 9이고, 정점 100만 개 그래프에서 음수 가중치를 허용하는 순간 연산 수가 다익스트라의 약 5만 배가 된다(원문 식 직접 계산 · 그림 5).
- 「경로 결과가 이상하다」는 가중치의 유무 · 부호 · 연결 여부로 가른다 — 가중치를 무시했으면 탐색을 쓴 것이고, 음수 간선이 있으면 최단 경로 전제 위반이며, 트리 간선이 정점 수 − 1 보다 적으면 그래프가 끊겨 있다.
2등장 배경
1950년대 전화망 · 송전망 설계자는 도시 수십 곳을 잇는 선로 조합이 너무 많아 하나씩 비교할 수 없었다. Kruskal 은 1956년 가장 짧은 간선부터 고리를 만들지 않게 고르는 방법을(Kruskal 1956), Prim 은 1957년 벨 연구소 논문에서 한 점에서 나무를 키우는 방법을 냈다(Prim 1957).
최단 경로는 같은 시기 수송 · 통신 경로 문제에서 나왔다. Bellman 은 1958년 동적 계획법으로 경로 문제를 풀었고(Bellman 1958), Dijkstra 는 1959년 세 쪽 논문 하나에 최소 신장 트리와 두 점 사이 최단 경로를 함께 실었다(Dijkstra 1959). Tarjan 은 1972년 깊이 우선 탐색 하나로 연결 성분 같은 문제를 선형 시간에 푸는 틀을 세웠다(Tarjan 1972).
지금은 이 절차들이 교과서 · 오픈소스 라이브러리에 정리되어 있어(NetworkX minimum_spanning_tree) 새로 짜는 일은 드물다. 실무의 일은 질문에 맞는 절차를 고르고 그 전제(가중치 부호 · 연결)를 지키는 것이다.
3쉽게 이해하기 — 다섯 섬을 맡은 군청 주무관
섬 다섯 개를 맡은 군청의 한 주무관은 섬 · 뱃길 지도 한 장으로 세 가지 일을 한다. 태풍 경보는 배 한 번에 닿는 섬부터 차례로 돌리고, 구급선은 운항 시간이 가장 짧은 뱃길로 보낸다. 섬을 모두 잇는 다리 공사는 견적서를 싼 순으로 쌓아 두고 위부터 승인하되, 이미 이어진 섬끼리 잇는 다리는 반려한다.
그림 1 · 같은 섬 지도 한 장으로 주무관이 세 가지 다른 질문을 풀며, 다리 공사는 싼 순으로 쌓은 견적서(정렬)를 받아 쓴다.
그림 2 · 견적서를 싼 순으로 쌓는 일(정렬)과 위부터 승인 · 반려하는 일(최소 신장 트리)의 경계 — 정렬이 끝나면 다리 공사는 «이미 이어졌나»만 묻는다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 섬 · 뱃길 지도 | 그래프(정점 · 간선 · 가중치) | 연결과 비용을 인접 리스트 · 인접 행렬로 적는다 |
| 한 주무관 | 질문별 절차 선택 | 다 닿기 · 싼 길 · 싼 연결 중 무엇을 묻는지 보고 고른다 |
| 경보 돌리기 | 그래프 탐색(BFS) | 출발점에서 간선 수가 적은 정점부터 큐로 방문한다 |
| 한 뱃길 끝까지 따라가기 | 그래프 탐색(DFS) | 갈 수 있는 데까지 들어갔다 되돌아오며 연결 성분을 가른다 |
| 구급선 뱃길 | 최단 경로(다익스트라) | 한 출발점에서 가중치 합이 가장 작은 경로를 정점마다 확정한다 |
| 시간이 줄어드는 뱃길 | 음수 가중치(벨만-포드) | 모든 간선을 V − 1 번 완화하고 음수 사이클을 검사한다 |
| 싼 순 견적서 더미 | 정렬 | 간선을 가중치 순으로 늘어놓는다(비교 정렬 하한 N lg N) |
| 다리 승인 · 반려 | 최소 신장 트리(크루스칼) | 고리를 만들지 않는 가장 싼 간선을 정점 수 − 1 개까지 고른다 |
⚠ 비유가 맞지 않는 곳: 실제 뱃길 시간은 날씨에 따라 바뀌지만 이 절차들은 가중치를 고정 값으로 받는다. 다리는 양쪽으로 건너지만 그래프에는 한 방향만 가는 간선(방향 그래프)도 있고, 그 경우 최소 신장 트리는 따로 정의된다.
4구조 — 세 질문과 공통 입력
아래 토픽 넷은 같은 입력(그래프 표현) 위에서 서로 다른 질문을 맡는다. 탐색은 가중치 없이 «닿는가 · 몇 간선 만에», 최단 경로는 한 출발점 기준 «가장 싼 길», 최소 신장 트리는 출발점 없이 «전체를 가장 싸게»를 묻고, 정렬은 크루스칼에 간선 순서를 넘긴다.
그림 3 · 세 질문은 같은 그래프 표현을 입력으로 받고, 가중치를 더하면 탐색이 최단 경로로, 출발점을 지우고 전체 연결을 물으면 최소 신장 트리로 넘어가며, 정렬은 크루스칼의 첫 단계가 된다.
| 아래 토픽 | 묻는 질문 | 입력 전제 | 결과 모양 | 비용(근거) |
|---|---|---|---|---|
| 그래프 탐색(BFS · DFS) | 닿는가 · 몇 간선 만에 | 가중치 없음 | 방문 순서 · BFS 트리 | V + E(Sedgewick · Wayne 4.1) |
| 최단 경로(다익스트라 · 벨만-포드) | 한 출발점에서 가장 싼 길 | 다익스트라 = 0 이상 · 벨만-포드 = 음수 사이클 없음 | 최단 경로 트리 | E log V · E V(Sedgewick · Wayne 4.4) |
| 최소 신장 트리(MST) | 모든 정점을 가장 싸게 | 무방향 · 연결 | 간선 V − 1 개 | E log E(Sedgewick · Wayne 4.3) |
| 정렬 | 간선을 가중치 순으로 | 비교 가능한 키 | 정렬된 간선 목록 | 하한 lg(N!) ~ N lg N(Sedgewick · Wayne 2.2) |
정렬은 그래프 알고리즘에서 «비교 기준»이다. 크루스칼의 E log E 는 간선 정렬 몫이 정하므로, 다른 그래프 알고리즘의 비용을 «정렬 한 번보다 싼가 비싼가»로 견줄 수 있다.
🔑 같은 그래프라도 «출발점이 있는 질문»은 최단 경로 트리를, «출발점이 없는 질문»은 최소 신장 트리를 내고, 두 트리는 일반적으로 다르다.
5동작 — 다섯 정점 그래프에 세 질문 던지기
설명용 가정 값 = 무방향 그래프 정점 5(S · A · B · C · D) · 간선 7(S–A 5 · S–B 3 · A–B 1 · A–C 2 · B–D 6 · C–D 4 · S–D 10 · 가중치 서로 다름).
- 인접 리스트로 저장한다 — 무방향 간선은 양 끝에 한 번씩 적어 목록 항목 14개 + 정점 5 = 19개이고, 인접 행렬이면 셀 25개다.
- S 에서 BFS 를 돌린다 — 큐에서 A · B · D 가 1간선, C 가 2간선(A 경유)으로 나온다. D 는 S–D 직항 1간선이지만 비용은 10이다(Sedgewick · Wayne 4.1).
- S 에서 다익스트라를 돌린다 — 확정 순서 S 0 → B 3 → A 4(S–A 5 보다 S–B–A 4) → C 6 → D 9(S–D 10 보다 S–B–D 9)(NIST DADS Dijkstra).
- 두 결과를 견준다 — S→D 가 BFS 로는 간선 1개 · 비용 10, 다익스트라로는 간선 2개 · 비용 9다.
- 간선 7개를 가중치 순으로 정렬한다 — A–B 1 · A–C 2 · S–B 3 · C–D 4 · S–A 5 · B–D 6 · S–D 10.
- 크루스칼로 앞에서부터 고른다 — A–B · A–C · S–B · C–D 를 채택하고 간선 4개(= 정점 5 − 1)에서 멈춘다. 합은 10이고 S–A · B–D · S–D 는 고리가 되어 버린다(NIST DADS Kruskal).
- 두 트리를 견준다 — 최단 경로 트리(S–B · B–A · A–C · B–D)는 합 12, 최소 신장 트리는 합 10이다. 최소 신장 트리 안에서 S→D 는 S–B–A–C–D 로 10이라 최단 9 보다 비싸다.
그림 4 · 같은 그래프에서 BFS 트리는 간선 수를, 최단 경로 트리는 S 기준 비용을, 최소 신장 트리는 전체 합을 줄이며, S→D 비용은 10 · 9 · 10 으로 갈린다.
🔑 «간선 수가 가장 적은 길», «한 점에서 가장 싼 길», «전체가 가장 싼 연결»은 세 다른 답이다 — 질문을 먼저 정하지 않으면 맞는 절차도 틀린 답을 낸다.
알고리즘 사이 비용 차이는 전제에서 나온다. 같은 그래프에서 가중치 조건을 약하게 할수록 쓸 수 있는 절차가 바뀌고 연산 수가 차수 단위로 뛴다.
그림 5 · 정점 100만 · 간선 300만 그래프에서 가중치가 없으면 약 400만 번, 0 이상이면 약 6,000만 번, 음수를 허용하면 3조 번으로 — 전제 하나가 연산 수를 5만 배 가른다.
🔑 음수 간선 하나가 다익스트라의 «꺼낸 정점은 다시 줄지 않는다»는 전제를 깨고, 그 대가로 모든 간선을 V − 1 번 다시 보는 벨만-포드 비용을 낸다.
6비교 — 관련 기술과의 경계
| 기술 | 맡는 일 | 경계 | 넘기는 곳 | 확인 자료 |
|---|---|---|---|---|
| 그래프 알고리즘 | 탐색 · 최단 경로 · MST · 정렬 | 그래프가 주어진 뒤의 절차 | 그래프 저장 방식 → 자료구조 | 정점 · 간선 수 · 가중치 범위 |
| 자료구조 | 그래프 · 힙 · 스택 · 큐 · 해시 테이블 | 넣기 · 빼기 · 찾기 한 번의 비용 | 힙을 쓰는 다익스트라 → 그래프 알고리즘 | 연산별 비용 |
| 알고리즘 설계 기법 | 분할 정복 · 동적 계획법 · 그리디 · A* | 절차를 세우는 방식 | 그리디 = 크루스칼 · 동적 계획법 = 벨만-포드 → 그래프 알고리즘 | 최적해 보장 조건 |
| 알고리즘 분석(계산 복잡도) | Big-O · P · NP | 비용을 재는 잣대 | 다항 시간 그래프 문제의 절차 → 그래프 알고리즘 | 증가 차수 |
| 라우팅 프로토콜 | OSPF · BGP 같은 경로 교환 규약 | 경로 정보를 장비끼리 주고받는 방식 | 각 장비 안의 최단 경로 계산 = 그래프 알고리즘의 절차 | 라우팅 표 |
| 그래프 신경망(GNN) | 그래프 데이터로 표현 학습 | 데이터로 맞춘 모델 | 이웃 방문 순서 = 탐색 · 정답이 정해진 계산 = 그래프 알고리즘 | 검증 오차 |
분석그래프가 주어지고 답이 하나로 정해지는 질문(닿는가 · 가장 싼 길 · 가장 싼 연결)은 그래프 알고리즘에서, 그래프를 어떻게 저장하느냐는 자료구조에서, 비용 차수 자체는 알고리즘 분석에서 본다. 근거는 표의 「경계」 열 — 같은 다익스트라라도 힙 연산 비용은 자료구조가 다루고 «가중치 0 이상» 전제는 그래프 알고리즘이 다룬다(NIST DADS Dijkstra).
7실무 진단 — 경로 결과가 이상할 때 하위 토픽 가르기
분석먼저 그래프가 끊겼는지와 가중치 부호를 보고, 그다음 고른 절차가 질문과 맞는지를 본다. 입력 전제가 깨진 상태에서는 어떤 절차도 맞는 답을 주지 않기 때문이다(NetworkX number_connected_components · NIST DADS Bellman-Ford).
| # | 증상 | 의심 원인 | 하위 토픽 | 확인 명령(NetworkX 3.7) | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | MST 간선 수가 V − 1 보다 적음 | 그래프가 끊김 → 신장 숲 | 그래프 탐색 · MST | nx. | 1 보다 크면 성분마다 트리(NetworkX minimum_ |
| 2 | 최단 경로 비용이 손 계산과 다름 | 음수 간선 · 음수 사이클 | 최단 경로 | nx. · 가중치 최솟값 | True 면 최단 경로 정의 불가 · 음수만 있으면 벨만-포드(NIST DADS Bellman-Ford) |
| 3 | 경로가 간선 수만 적고 비쌈 | 가중치 속성 누락 · 이름 틀림 | 그래프 탐색 · 최단 경로 | G.edges(data=True) 로 weight 키 확인 | 키가 없으면 가중치 1 로 처리되어 BFS 와 같은 답(NetworkX minimum_ |
| 4 | 같은 입력인데 MST 가 실행마다 다름 | 같은 가중치 간선 | MST · 정렬 | 가중치 중복 수 세기 | 중복이 있으면 MST 가 하나가 아닐 수 있음 · 합은 같음(Sedgewick · Wayne 4.3) |
1 · 2행은 입력 전제 문제라 3 · 4행보다 먼저 본다. 4행은 오류가 아니라 정렬의 동률 처리 차이이므로 합을 먼저 비교한다.
8시험 대비
시험에서는 다익스트라와 벨만-포드, 크루스칼과 프림을 견주는 비교형, 그리고 작은 그래프에 절차를 적용해 단계별 표를 쓰게 하는 동작 · 절차 설명형으로 나올 수 있다. 어느 쪽이든 «질문 → 전제 → 절차 → 비용» 순서로 쓰면 비교 축이 저절로 생긴다.
- 개요 — 정점 · 간선 · 가중치로 적은 연결 구조 · 세 질문(탐색 · 최단 경로 · MST) · 1956 ~ 1959 원 논문
- 구성 — 그림 3 질문별 알고리즘 + 아래 토픽 표(전제 · 결과 모양 · 비용)
- 절차 — 그림 4 다섯 정점 사례(BFS 간선 수 · 다익스트라 확정 순서 · 크루스칼 채택 · 고리 제외)
- 비교 — 다익스트라 · 벨만-포드(음수 가중치 · E log V ↔ E V) · 크루스칼 · 프림(간선 정렬 ↔ 정점에서 확장)
- 핵심 원리 — 그림 5 전제별 연산 수(가중치 없음 · 0 이상 · 음수 허용)
- 적용 — 라우팅 경로 계산 · 배선 · 망 설계의 최소 연결
꼭 쓸 키워드
인접 리스트BFSDFS완화다익스트라벨만-포드음수 사이클절단 성질크루스칼프림
다른 답안과 차이를 내는 한 가지는 그림 4 처럼 같은 그래프에서 최단 경로 트리(합 12)와 최소 신장 트리(합 10)가 다르게 나오는 것을 수치로 보이는 것이다.
9오해와 사실
- 오해최소 신장 트리 안의 경로가 곧 최단 경로다.사실최소 신장 트리는 전체 합을 줄일 뿐 출발점이 없어, 사례에서 S→D 가 트리 안에서는 10, 최단으로는 9다(Sedgewick · Wayne 4.3).
- 오해다익스트라는 음수 가중치가 몇 개 있어도 대체로 맞는다.사실정점을 꺼낼 때 확정하는 방식은 가중치 0 이상을 전제로 하며 음수 간선에서 틀린 답을 낼 수 있다(NIST DADS Dijkstra · Sedgewick · Wayne 4.4).
- 오해BFS 는 가중치가 없을 때만 쓰는 낡은 방법이다.사실가중치가 모두 같으면 BFS 가 간선 수 기준 최단 경로를 V + E 시간에 주며 다익스트라보다 싸다(Sedgewick · Wayne 4.1).
10핵심 정리
| 하위 토픽 | 질문 | 전제 | 결과 | 비용 | 쓰는 곳 |
|---|---|---|---|---|---|
| BFS | 몇 간선 만에 닿나 | 가중치 없음 · 같음 | 간선 수 최단 트리 | V + E | 홉 수 · 전파 범위 |
| DFS | 어디까지 이어졌나 | 없음 | 방문 · 종료 순서 | V + E | 연결 성분 · 사이클 검사 |
| 다익스트라 | 한 점에서 가장 싼 길 | 가중치 0 이상 | 최단 경로 트리 | E log V | 지도 길찾기 · 링크 상태 라우팅 |
| 벨만-포드 | 음수가 있어도 가장 싼 길 | 음수 사이클 없음 | 최단 경로 트리 · 사이클 판정 | E V | 음수 비용 · 거리 벡터 |
| 크루스칼 · 프림 | 전체를 가장 싸게 | 무방향 · 연결 | 간선 V − 1 개 | E log E · E log V | 배선 · 망 설계 |
| 정렬 | 간선 순서 맞추기 | 비교 가능한 키 | 정렬된 간선 | 하한 N lg N | 크루스칼 첫 단계 · 비교 기준 |
11참고 문헌
- 먼저 볼 문헌
- ★ Algorithms 4th Edition (Sedgewick · Wayne) 4.1 Undirected Graphs — BFS · DFS 가 V + E 에 비례하는 시간에 끝나고 BFS 가 «간선 수가 가장 적은 경로»를 주는 근거를 볼 때
- ★ Algorithms 4th Edition (Sedgewick · Wayne) 4.4 Shortest Paths — 다익스트라(E log V) · 벨만-포드(E V) · 비순환 그래프(E + V)의 전제와 비용을 나란히 볼 때
- ★ Algorithms 4th Edition (Sedgewick · Wayne) 4.3 Minimum Spanning Trees — 절단 성질 · 같은 가중치일 때 MST 가 하나가 아닐 수 있다는 점 · 크루스칼 E log E 를 볼 때
- ★ Dictionary of Algorithms and Data Structures - Bellman-Ford algorithm — V − 1 번 완화 뒤 한 번 더 돌려 음수 사이클을 찾는 절차를 볼 때
- ★ NetworkX 3.7 documentation - minimum_spanning_tree — 끊긴 그래프에서 신장 숲이 나오는 것 · 가중치 속성이 없을 때 1 로 보는 것을 확인할 때
- 본문 근거
- Algorithms 4th Edition (Sedgewick · Wayne) 2.2 Mergesort - compare-based sorting lower bound — Princeton University · 2026-11 ·
algs4.cs.princeton.edu/22mergesort/· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - Dijkstra's algorithm — NIST · 2024-05 ·
xlinux.nist.gov/dads/HTML/dijkstraalgo.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - Kruskal's algorithm — NIST · 2024-08 ·
xlinux.nist.gov/dads/HTML/kruskalsalgo.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - minimum spanning tree — NIST · 2022-07 ·
xlinux.nist.gov/dads/HTML/minimumSpanningTree.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - breadth-first search — NIST · 2019-04 ·
xlinux.nist.gov/dads/HTML/breadthfirst.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - depth-first search — NIST · 2021-10 ·
xlinux.nist.gov/dads/HTML/depthfirst.html· 확인 2026-11-14 - NetworkX 3.7 documentation - negative_edge_cycle — NetworkX Developers · 2026-11 ·
networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.negative_edge_cycle.html· 확인 2026-11-14 - NetworkX 3.7 documentation - number_connected_components — NetworkX Developers · 2026-11 ·
networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.number_connected_components.html· 확인 2026-11-14 - Kruskal 1956 On the shortest spanning subtree of a graph and the traveling salesman problem (Proceedings of the AMS 7(1) · 48-50) — American Mathematical Society · 1956-02 ·
doi.org/10.1090/S0002-9939-1956-0078686-7· 확인 2026-11-14 - Prim 1957 Shortest Connection Networks And Some Generalizations (Bell System Technical Journal 36(6) · 1389-1401) — AT&T · IEEE · 1957-11 ·
doi.org/10.1002/j.1538-7305.1957.tb01515.x· 확인 2026-11-14 - Bellman 1958 On a routing problem (Quarterly of Applied Mathematics 16(1) · 87-90) — American Mathematical Society · 1958-04 ·
doi.org/10.1090/qam/102435· 확인 2026-11-14 - A Note on Two Problems in Connexion with Graphs (E. W. Dijkstra · Numerische Mathematik 1 · 269-271) — Springer · EuDML 기록 · 1959-12 ·
eudml.org/doc/131436· 확인 2026-11-14 - Tarjan 1972 Depth-First Search and Linear Graph Algorithms (SIAM Journal on Computing 1(2) · 146-160) — SIAM · 1972-06 ·
doi.org/10.1137/0201010· 확인 2026-11-14