C++ 그래프 알고리즘: BFS·DFS, 다익스트라, Kruskal·Prim 최소신장트리, Union-Find
그래프 문제에서 가장 비싼 실수는 구현 버그보다 알고리즘 선택을 잘못하는 것입니다. 가중치가 있는 도로망에서 DFS로 모든 경로를 열거하면 경로 수가 정점 수에 대해 지수적으로 늘어나므로, 수천 개 교차로만 되어도 끝나지 않습니다. 같은 문제를 다익스트라로 풀면 O(E log V)에 끝납니다. 이 글은 먼저 어떤 상황에 어떤 알고리즘이 맞는지 정리한 다음, BFS·DFS·위상 정렬·다익스트라·Union-Find·최소신장트리를 C++로 구현하고, 실제로 자주 틀리는 지점을 짚습니다.
그래프 알고리즘이 필요한 상황들
지도 앱 최단 경로
교차로 5,000개와 도로 2만 개가 있는 도시에서 A에서 B까지의 최단 거리를 구한다고 해 봅시다. 도로마다 길이(가중치)가 다르므로 간선 개수만 세는 BFS로는 답이 나오지 않고, 모든 경로를 DFS로 열거하는 방식은 지수 시간이 걸립니다. 가중치가 음이 아니라면 다익스트라가 맞는 도구입니다.
소셜 네트워크 “친구의 친구” 탐색
사용자 A로부터 3단계 이내에 있는 모든 사용자를 찾는 문제는 “거리”가 간선 개수로 정의됩니다. BFS는 시작점에서 가까운 정점부터 레벨 순서로 방문하므로, 레벨 3까지만 확장하면 됩니다. DFS는 한 방향으로 깊이 들어가기 때문에 먼저 도달한 경로가 가장 짧은 경로라는 보장이 없습니다.
빌드 시스템 의존성 순서
모듈 A가 B에, B가 C에 의존한다면 C, B, A 순으로 빌드해야 합니다. 이 순서를 구하는 것이 위상 정렬이고, 같은 과정에서 순환 의존성(사이클)도 감지할 수 있습니다. DFS 기반과 진입 차수 기반(Kahn) 두 가지 방법이 있습니다.
네트워크 케이블 최소 비용 배치
건물 100개를 모두 연결하되 케이블 비용 합을 최소로 하는 문제는 최소신장트리(MST) 문제입니다. 간선을 싼 것부터 고르는 Kruskal이나, 한 정점에서 트리를 키워 나가는 Prim을 씁니다.
게임 AI 경로 탐색 (2D 그리드)
탑뷰 게임에서 유닛이 장애물을 피해 목표 칸까지 이동하는데, 모든 이동 비용이 같다면 각 칸을 정점, 상하좌우 이동을 간선으로 보고 BFS를 돌리면 최소 이동 횟수를 O(V+E)에 구할 수 있습니다. 맵이 커서 목표 방향으로 탐색을 좁히고 싶다면 A*를 고려하지만, 그 출발점도 BFS·다익스트라입니다.
동적 연결성 확인
친구 관계가 계속 추가되는 상황에서 “두 사용자가 같은 그룹인가?”를 반복해서 묻는다면, 질의마다 BFS를 돌리는 방식은 O(V+E) × 질의 수가 됩니다. Union-Find는 합치기와 찾기를 모두 거의 상수 시간에 처리하며, Kruskal 알고리즘의 핵심 부품이기도 합니다.
알고리즘 선택 표
| 문제 유형 | 알고리즘 | 시간 복잡도 |
|---|---|---|
| 최단 경로 (가중치 ≥ 0) | 다익스트라 | O(E log V) |
| 최단 경로 (가중치 없음) | BFS | O(V + E) |
| 최단 경로 (음수 간선 있음) | 벨만-포드 | O(V·E) |
| 연결 요소, 사이클 탐지 | DFS | O(V + E) |
| 동적 연결성 | Union-Find | 연산당 O(α(n)) |
| 위상 정렬 | DFS 또는 Kahn | O(V + E) |
| 최소 연결 비용 | Kruskal / Prim | O(E log E) / O(E log V) |
인접 리스트와 인접 행렬
flowchart LR
subgraph adj_list[인접 리스트]
L1[정점 0] --> L2[1, 2, 3]
L3[정점 1] --> L4[0, 2]
L5[정점 2] --> L6[0, 1]
end
subgraph adj_matrix[인접 행렬]
M1["0 1 1 1"]
M2["1 0 1 0"]
M3["1 1 0 0"]
end
인접 리스트는 공간이 O(V + E)이고 한 정점의 이웃을 차수만큼의 시간에 순회합니다. 간선이 정점 수에 비해 적은 희소 그래프, 즉 도로망이나 소셜 그래프 대부분에 맞습니다. 인접 행렬은 공간이 O(V²)이지만 “u와 v 사이에 간선이 있는가”를 O(1)에 답합니다. 정점이 수천 개를 넘으면 행렬 자체가 메모리를 크게 차지하므로, 밀집 그래프이거나 플로이드-워셜처럼 행렬 연산이 자연스러운 알고리즘에서만 고르는 편이 낫습니다.
#include <vector>
#include <utility>
// 가중치 있는 그래프: adj[v] = {(u, weight), ...}
using Graph = std::vector<std::vector<std::pair<int, int>>>;
// 가중치 없는 그래프
using SimpleGraph = std::vector<std::vector<int>>;
// 무방향 그래프 예: 간선 (0-1, 2), (1-2, 3), (0-2, 5)
Graph buildGraph() {
Graph g(3);
auto add = [&](int u, int v, int w) {
g[u].emplace_back(v, w);
g[v].emplace_back(u, w); // 무방향이므로 양쪽에 추가
};
add(0, 1, 2);
add(1, 2, 3);
add(0, 2, 5);
return g;
}무방향 그래프는 간선 하나를 양쪽 리스트에 모두 넣어야 합니다. 한쪽만 넣으면 방향 그래프가 되어 탐색 결과가 조용히 달라지는데, 에러가 나지 않아 발견이 늦습니다.
BFS 너비 우선 탐색
BFS는 큐를 사용해 시작점에서 거리 1인 정점을 모두 방문한 뒤 거리 2로 넘어갑니다. 큐가 거리 순서를 유지하므로, 가중치 없는 그래프에서는 어떤 정점에 처음 도달한 순간의 거리가 최단 거리입니다.
flowchart TD A[시작 0] --> B[1] A --> C[2] B --> D[3] B --> E[4] C --> E D --> F[5] E --> F
위 그래프의 BFS 방문 순서는 0, 그다음 레벨 1(1, 2), 레벨 2(3, 4), 레벨 3(5)입니다.
#include <vector>
#include <queue>
#include <algorithm>
// 반환: 각 정점까지의 거리(간선 개수), 도달 불가 시 -1
std::vector<int> bfs(const SimpleGraph& g, int start) {
const int n = static_cast<int>(g.size());
std::vector<int> dist(n, -1);
std::queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[v] == -1) { // 큐에 넣는 시점에 방문 표시
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
// 경로 복원이 필요하면 parent 배열을 함께 유지
struct BFSResult {
std::vector<int> dist;
std::vector<int> parent; // parent[v] = u: u에서 v로 왔음
};
BFSResult bfsWithPath(const SimpleGraph& g, int start) {
const int n = static_cast<int>(g.size());
BFSResult res;
res.dist.assign(n, -1);
res.parent.assign(n, -1);
std::queue<int> q;
res.dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (res.dist[v] == -1) {
res.dist[v] = res.dist[u] + 1;
res.parent[v] = u;
q.push(v);
}
}
}
return res;
}
// parent를 거꾸로 따라가 start → end 경로 복원
std::vector<int> restorePath(const std::vector<int>& parent, int start, int end) {
std::vector<int> path;
for (int v = end; v != -1; v = parent[v]) {
path.push_back(v);
}
std::reverse(path.begin(), path.end());
if (!path.empty() && path[0] == start) return path;
return {}; // 도달 불가
}방문 표시를 큐에서 꺼낼 때가 아니라 넣을 때 하는 점이 중요합니다. 꺼낼 때 표시하면 같은 정점이 여러 이웃에게서 중복으로 큐에 들어가 큐 크기가 간선 수만큼 커질 수 있습니다.
SimpleGraph g(6);
g[0] = {1, 2}; g[1] = {0, 3, 4}; g[2] = {0, 4};
g[3] = {1, 5}; g[4] = {1, 2, 5}; g[5] = {3, 4};
auto res = bfsWithPath(g, 0);
auto path = restorePath(res.parent, 0, 5); // {0, 1, 3, 5}, 거리 3거리 3인 최단 경로는 0-1-3-5와 0-1-4-5, 0-2-4-5 등 여러 개지만, 이 코드는 인접 리스트 순서상 5를 3에서 먼저 발견하므로 항상 {0, 1, 3, 5}를 돌려줍니다. 최단 경로가 여러 개일 때 어느 것이 나오는지는 인접 리스트 순서에 달려 있습니다.
DFS 깊이 우선 탐색
DFS는 한 방향으로 끝까지 들어갔다가 막히면 되돌아옵니다. 최단 거리는 주지 않지만, 연결 요소 찾기, 사이클 감지, 위상 정렬처럼 “끝까지 들어갔다 나오는 순서”가 의미를 가지는 문제에 씁니다.
#include <vector>
// 재귀 DFS
void dfsRecursive(const SimpleGraph& g, int u, std::vector<bool>& visited,
std::vector<int>& order) {
visited[u] = true;
order.push_back(u);
for (int v : g[u]) {
if (!visited[v]) {
dfsRecursive(g, v, visited, order);
}
}
}
// 명시적 스택 DFS (깊은 그래프에서 호출 스택 오버플로우를 피함)
std::vector<int> dfsIterative(const SimpleGraph& g, int start) {
const int n = static_cast<int>(g.size());
std::vector<bool> visited(n, false);
std::vector<int> order;
std::vector<int> stack{start};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
if (visited[u]) continue; // 여러 번 push된 정점은 여기서 걸러짐
visited[u] = true;
order.push_back(u);
// 역순으로 넣어야 재귀 버전과 같은 방문 순서가 됨
for (auto it = g[u].rbegin(); it != g[u].rend(); ++it) {
if (!visited[*it]) stack.push_back(*it);
}
}
return order;
}
// 연결 요소 개수
int countComponents(const SimpleGraph& g) {
const int n = static_cast<int>(g.size());
std::vector<bool> visited(n, false);
std::vector<int> order;
int count = 0;
for (int i = 0; i < n; ++i) {
if (!visited[i]) {
++count;
dfsRecursive(g, i, visited, order);
}
}
return count;
}반복 버전은 꺼낼 때 방문 표시를 하므로 한 정점이 스택에 여러 번 들어갈 수 있고, 스택 크기가 최악의 경우 O(E)까지 커집니다. 대신 재귀 버전과 같은 순서로 방문합니다. 이웃을 정방향으로 넣으면 순서가 뒤집히는데, 그래도 탐색 자체는 올바르지만 결과를 재귀 버전과 비교하는 테스트가 깨지는 원인이 되곤 합니다.
무방향 그래프 사이클 감지
bool hasCycleUndirected(const SimpleGraph& g, int u, int parent,
std::vector<bool>& visited) {
visited[u] = true;
for (int v : g[u]) {
if (!visited[v]) {
if (hasCycleUndirected(g, v, u, visited)) return true;
} else if (v != parent) {
return true; // 부모가 아닌 방문 정점을 다시 만남 → 사이클
}
}
return false;
}
bool hasCycle(const SimpleGraph& g) {
const int n = static_cast<int>(g.size());
std::vector<bool> visited(n, false);
for (int i = 0; i < n; ++i) {
if (!visited[i] && hasCycleUndirected(g, i, -1, visited)) return true;
}
return false;
}부모 정점을 정점 번호로 비교하기 때문에, 같은 두 정점 사이에 간선이 두 개 있는 다중 그래프에서는 길이 2짜리 사이클을 놓칩니다. 다중 간선을 허용해야 한다면 부모 정점 대신 들어온 간선의 번호를 기억해야 합니다.
위상 정렬 (DAG)
방향 그래프에서는 부모 비교 대신 세 가지 색을 씁니다. White는 미방문, Gray는 현재 재귀 경로 위에 있는 정점, Black은 탐색이 끝난 정점입니다. Gray 정점을 다시 만나면 뒤로 가는 간선이 있다는 뜻이고, 그것이 곧 사이클입니다.
#include <algorithm>
enum class Color { White, Gray, Black };
bool topoSortDFS(const SimpleGraph& g, int u, std::vector<Color>& color,
std::vector<int>& order) {
color[u] = Color::Gray;
for (int v : g[u]) {
if (color[v] == Color::Gray) return false; // 사이클
if (color[v] == Color::White && !topoSortDFS(g, v, color, order)) {
return false;
}
}
color[u] = Color::Black;
order.push_back(u); // 후위 순서로 기록
return true;
}
// 사이클이 있으면 빈 벡터
std::vector<int> topologicalSort(const SimpleGraph& g) {
const int n = static_cast<int>(g.size());
std::vector<Color> color(n, Color::White);
std::vector<int> order;
for (int i = 0; i < n; ++i) {
if (color[i] == Color::White && !topoSortDFS(g, i, color, order)) {
return {};
}
}
std::reverse(order.begin(), order.end()); // 후위 순서의 역순이 위상 순서
return order;
}진입 차수가 0인 정점부터 큐에 넣고 꺼내면서 이웃의 진입 차수를 줄여 가는 Kahn 알고리즘도 같은 O(V+E)입니다. Kahn 방식에서는 사이클에 속한 정점의 진입 차수가 끝까지 0이 되지 않으므로, 결과 길이가 V보다 짧으면 사이클이 있다고 판단합니다. 무한 루프에 빠지지는 않지만, 결과 길이를 확인하지 않으면 일부 정점이 빠진 순서를 정상 결과로 착각하게 됩니다.
다익스트라 최단 경로
다익스트라는 가중치가 음이 아닌 그래프에서 한 출발점으로부터 모든 정점까지의 최단 거리를 구합니다. 우선순위 큐에서 현재까지 가장 가까운 정점을 꺼내 확정하고, 그 정점에서 나가는 간선으로 이웃의 거리를 줄여 나갑니다.
flowchart LR A[시작] -->|2| B A -->|5| C B -->|3| C B -->|1| D C -->|1| D
#include <vector>
#include <queue>
#include <limits>
#include <functional>
constexpr int INF = std::numeric_limits<int>::max();
struct DijkstraResult {
std::vector<int> dist;
std::vector<int> parent;
};
DijkstraResult dijkstra(const Graph& g, int start) {
const int n = static_cast<int>(g.size());
DijkstraResult res;
res.dist.assign(n, INF);
res.parent.assign(n, -1);
// (거리, 정점) 최소 힙
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<>> pq;
res.dist[start] = 0;
pq.emplace(0, start);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > res.dist[u]) continue; // 더 짧은 거리로 이미 처리된 낡은 항목
for (const auto& [v, w] : g[u]) {
int newDist = res.dist[u] + w;
if (newDist < res.dist[v]) {
res.dist[v] = newDist;
res.parent[v] = u;
pq.emplace(newDist, v);
}
}
}
return res;
}std::priority_queue에는 원소의 우선순위를 낮추는 decrease-key 연산이 없습니다. 그래서 거리가 갱신될 때마다 새 항목을 넣고, 꺼낸 항목이 이미 낡았으면 d > dist[u]로 건너뜁니다. 큐에는 최대 E개 항목이 쌓이므로 전체 복잡도는 O(E log E)이고, E ≤ V²이라 log E ≤ 2 log V이므로 O(E log V)와 같습니다.
// 방향 그래프: 0→1(2), 0→2(4), 1→2(1), 1→3(7), 2→3(3), 3→4(1)
Graph g(5);
g[0].emplace_back(1, 2); g[0].emplace_back(2, 4);
g[1].emplace_back(2, 1); g[1].emplace_back(3, 7);
g[2].emplace_back(3, 3); g[3].emplace_back(4, 1);
auto res = dijkstra(g, 0);
// res.dist == {0, 2, 3, 6, 7}
// restorePath(res.parent, 0, 4) == {0, 1, 2, 3, 4}0에서 2로 바로 가면 4지만 1을 거치면 2+1=3이 되어 더 짧습니다. 우선순위 큐가 거리 2인 정점 1을 먼저 꺼내기 때문에 정점 2는 거리 4로 확정되기 전에 3으로 갱신됩니다.
Union-Find (분리 집합)
Union-Find는 원소들을 겹치지 않는 집합으로 나누어 관리합니다. find(x)는 x가 속한 집합의 대표 원소를 돌려주고, unite(x, y)는 두 집합을 합칩니다. 각 집합을 트리로 표현하고 루트를 대표로 씁니다.
flowchart LR
subgraph before[unite 전]
A1["{0,1,2}"]
B1["{3,4}"]
end
subgraph after["unite(1,3) 후"]
C1["{0,1,2,3,4}"]
end
#include <vector>
#include <numeric>
#include <utility>
// 경로 압축 + 랭크 기반 합치기: 연산당 분할 상환 O(α(n))
class UnionFind {
std::vector<int> parent, rank_;
public:
explicit UnionFind(int n) : parent(n), rank_(n, 0) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 경로 압축
return parent[x];
}
bool unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false; // 이미 같은 집합
if (rank_[px] < rank_[py]) std::swap(px, py);
parent[py] = px; // 낮은 트리를 높은 트리 밑에
if (rank_[px] == rank_[py]) ++rank_[px];
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
};두 최적화의 역할은 다릅니다. 랭크 기반 합치기만 써도 트리 높이가 O(log n)으로 제한되고, 경로 압축만 써도 분할 상환 O(log n) 수준이 됩니다. 둘을 함께 써야 역 아커만 함수 α(n)이 되는데, 이 값은 현실적인 n에서 4 이하라 사실상 상수입니다. 둘 다 빼면 한 줄로 길게 늘어선 트리가 생겨 find가 O(n)이 됩니다. find의 재귀 경로 압축은 트리가 이미 깊게 만들어진 상태에서 호출되면 재귀 깊이가 커질 수 있는데, 랭크 기반 합치기를 함께 쓰면 깊이가 O(log n)으로 묶이므로 문제가 되지 않습니다.
// 간선 목록이 주어졌을 때 연결 요소 개수: 루트의 개수
int countComponents(int n, const std::vector<std::pair<int, int>>& edges) {
UnionFind uf(n);
for (const auto& [u, v] : edges) uf.unite(u, v);
int count = 0;
for (int i = 0; i < n; ++i) {
if (uf.find(i) == i) ++count;
}
return count;
}
// 정점 5개, 간선 (0,1), (1,2), (3,4) → {0,1,2}, {3,4}로 2개
// 무방향 그래프 사이클 감지: 이미 같은 집합인 두 정점을 잇는 간선이 사이클을 만듦
bool hasCycleWithUnionFind(int n, const std::vector<std::pair<int, int>>& edges) {
UnionFind uf(n);
for (const auto& [u, v] : edges) {
if (!uf.unite(u, v)) return true;
}
return false;
}최소신장트리: Kruskal과 Prim
Kruskal
간선을 비용 오름차순으로 정렬한 뒤, 두 끝점이 아직 다른 집합에 있을 때만 간선을 채택합니다. 같은 집합에 있다면 이미 경로가 있다는 뜻이므로 그 간선은 사이클을 만듭니다. 이 판정에 위의 Union-Find를 씁니다.
#include <algorithm>
struct Edge {
int u, v, weight;
bool operator<(const Edge& e) const { return weight < e.weight; }
};
// MST 간선 목록과 총 비용. 그래프가 연결되어 있지 않으면 최소 신장 포레스트가 됨
std::pair<std::vector<Edge>, long long> kruskal(int n, std::vector<Edge> edges) {
std::sort(edges.begin(), edges.end());
UnionFind uf(n);
std::vector<Edge> mst;
long long totalCost = 0;
for (const auto& e : edges) {
if (uf.unite(e.u, e.v)) {
mst.push_back(e);
totalCost += e.weight;
if (static_cast<int>(mst.size()) == n - 1) break; // 간선 n-1개면 완성
}
}
return {mst, totalCost};
}복잡도는 정렬이 지배하므로 O(E log E)입니다. 반환된 간선이 n-1개보다 적으면 그래프가 연결되어 있지 않다는 뜻이므로, “모든 건물을 연결할 수 있는가”를 함께 판단할 수 있습니다.
std::vector<Edge> edges = {{0,1,2},{0,2,5},{1,2,3},{1,3,4},{2,3,1}};
auto [mst, cost] = kruskal(4, edges);
// 정렬 순서: 2-3(1), 0-1(2), 1-2(3), 1-3(4), 0-2(5)
// 채택: 2-3, 0-1, 1-2 → cost == 6Prim
한 정점에서 시작해, 이미 트리에 포함된 정점 집합과 바깥 정점을 잇는 간선 중 가장 싼 것을 반복해서 추가합니다. 다익스트라와 구조가 거의 같지만, 우선순위가 “시작점까지의 거리”가 아니라 “트리까지 잇는 간선 하나의 비용”이라는 점이 다릅니다.
// 무방향 인접 리스트 그래프에서 start가 속한 연결 요소의 MST 비용
long long prim(const Graph& g, int start = 0) {
const int n = static_cast<int>(g.size());
std::vector<bool> inMST(n, false);
std::vector<int> minEdge(n, INF);
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int>>,
std::greater<>> pq;
minEdge[start] = 0;
pq.emplace(0, start);
long long totalCost = 0;
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (inMST[u]) continue;
inMST[u] = true;
totalCost += w;
for (const auto& [v, weight] : g[u]) {
if (!inMST[v] && weight < minEdge[v]) {
minEdge[v] = weight;
pq.emplace(weight, v);
}
}
}
return totalCost;
}간선 목록이 이미 있고 정렬이 쉬운 경우에는 Kruskal이, 인접 리스트가 이미 있고 간선이 많은 밀집 그래프에서는 Prim이 다루기 편합니다. Prim은 시작 정점이 속한 연결 요소만 덮으므로, 연결되지 않은 그래프라면 inMST가 모두 true인지 확인해야 합니다.
도시 연결 비용과 최단 경로를 함께 구하기
같은 도로망에 Kruskal과 다익스트라를 모두 적용하면, “모든 도시를 잇는 최소 공사 비용”과 “도시 0에서 각 도시까지의 최단 거리”가 서로 다른 질문이라는 점이 드러납니다. 위에서 정의한 UnionFind, Edge, kruskal, dijkstra를 그대로 씁니다.
int main() {
const int n = 4;
std::vector<Edge> edges = {{0,1,2},{0,2,5},{1,2,3},{1,3,4},{2,3,1}};
Graph g(n);
for (const auto& e : edges) { // 무방향이므로 양쪽에 추가
g[e.u].emplace_back(e.v, e.weight);
g[e.v].emplace_back(e.u, e.weight);
}
auto [mst, cost] = kruskal(n, edges); // cost == 6
auto res = dijkstra(g, 0); // res.dist == {0, 2, 5, 6}
return 0;
}이 작은 예에서는 MST 위의 경로 길이(0-1-2-3 = 6)가 최단 거리와 우연히 같지만, 일반적으로 MST 위의 경로가 최단 경로라는 보장은 없습니다. 예를 들어 세 정점이 비용 1, 1, 1.5인 삼각형을 이루면 MST는 비용 1인 두 간선을 고르고, 비용 1.5인 간선 양 끝 사이의 MST 경로 길이는 2가 됩니다. MST는 간선 합 전체를 최소화할 뿐 특정 두 점 사이의 거리를 최소화하지 않습니다.
자주 틀리는 지점
다익스트라에 음수 간선
다익스트라는 큐에서 꺼낸 정점의 거리가 확정된다고 가정합니다. 음수 간선이 있으면 이미 확정한 정점으로 나중에 더 짧게 도달할 수 있어 이 가정이 깨지고, 결과가 틀려도 아무 에러가 나지 않습니다. 저는 그래프를 입력받는 단계에서 음수 가중치를 검사하고, 있으면 벨만-포드로 넘기는 편을 택합니다. 벨만-포드는 V-1번 모든 간선을 완화한 뒤 한 번 더 완화가 일어나면 음수 사이클이 있다고 판정합니다.
방문 체크 없이 큐에 넣기
// 잘못된 패턴: 무방향 그래프에서 0→1→0→1... 무한히 반복
for (int v : g[u]) q.push(v);
// 올바른 패턴
for (int v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}무방향 그래프에서는 u의 이웃 v의 리스트에 u가 다시 들어 있으므로, 방문 체크가 없으면 두 정점 사이를 영원히 오갑니다.
낡은 우선순위 큐 항목 건너뛰기 누락
if (d > dist[u]) continue;를 빼도 가중치가 음이 아니면 결과는 맞습니다. 낡은 항목으로 이웃을 다시 완화해도 더 짧은 값이 나오지 않기 때문입니다. 대신 같은 정점의 인접 리스트를 여러 번 순회하게 되어, 차수가 큰 정점이 많은 그래프에서는 눈에 띄게 느려집니다.
거리 합 오버플로우
거리를 int로 두면 가중치가 큰 경로에서 합이 INT_MAX를 넘어 음수로 바뀝니다. 부호 있는 정수 오버플로우는 C++에서 미정의 동작이기도 합니다. newDist만 long long으로 바꾸는 것으로는 부족하고, dist 배열과 INF까지 long long으로 바꿔야 합니다. 또 INF를 최댓값으로 잡으면 INF + w가 넘치므로, 도달하지 않은 정점에서 완화하지 않도록 하거나 INF를 최댓값보다 충분히 작게 잡습니다. 위 코드는 큐에서 꺼낸 정점만 완화하므로 dist[u]가 INF인 경우가 없습니다.
깊은 재귀로 인한 스택 오버플로우
일직선 모양의 그래프에서 재귀 DFS는 깊이가 V까지 갑니다. 기본 스택 크기는 Windows에서 1MB, 많은 Linux 배포판에서 8MB 정도라, 정점이 수십만 개인 경로 그래프라면 재귀 DFS가 스택을 넘기 쉽습니다. 이럴 때는 앞의 명시적 스택 DFS를 씁니다.
1-based 입력
문제 입력이 정점을 1부터 n까지 주는데 Graph g(n)으로 만들면 g[n] 접근이 범위를 벗어납니다. 입력을 받을 때 u - 1, v - 1로 변환하거나 Graph g(n + 1)로 만들고 0번을 비워 두는 방식 중 하나로 통일합니다.
그래프를 값으로 전달
std::vector<int> bfs(SimpleGraph g, int start)처럼 값으로 받으면 호출할 때마다 인접 리스트 전체가 복사됩니다. 읽기만 하는 알고리즘이라면 const SimpleGraph&로 받습니다.