방향 그래프(directed graph)가 주어졌을 때, 그래프의 모든 정점 쌍 (i, j)에 대해 정점 j가 정점 i에서 도달 가능한지(reachable) 판별해야 하는 경우가 많습니다. 여기서 '도달 가능'이란 정점 i에서 정점 j로 가는 경로(path)가 존재한다는 뜻입니다. 이러한 도달 가능 여부를 행렬 형태로 나타낸 것이 바로 전이 폐쇄(transitive closure)이며, 워셜 알고리즘(Warshall's Algorithm)은 주어진 그래프 G의 전이 폐쇄를 구하는 데 가장 널리 사용되는 방법입니다. 이번 글에서는 알고리즘의 원리와 함께 C++ 구현 예제를 단계별로 살펴보겠습니다.
워셜 알고리즘의 기본 원리
워셜 알고리즘은 동적 계획법(dynamic programming)에 기반한 알고리즘으로, 세 개의 중첩 반복문을 사용해 모든 정점 쌍 사이의 도달 가능성을 O(V³)의 시간 복잡도로 계산합니다. 핵심 아이디어는 다음과 같습니다.
- 그래프의 각 정점 k를 차례대로 '중간 경유지'로 고려합니다.
- 정점 i에서 k로 가는 경로가 있고, k에서 j로 가는 경로도 있다면 정점 i에서 j로 도달할 수 있습니다.
- 이 과정을 모든 정점에 대해 적용하면 최종적으로 완전한 전이 폐쇄 행렬을 얻을 수 있습니다.
알고리즘
시작
1. 그래프의 최대 노드 개수를 입력받는다.
2. 노드를 a, b, c … 순서로 라벨링한다.
3. 노드 사이에 간선이 존재하는지 검사하여 인접 행렬을 구성한다.
for i = 97부터 (97 + 노드 수) 미만까지
for j = 97부터 (97 + 노드 수) 미만까지
간선이 존재하면 adj[i - 97][j - 97] = 1
존재하지 않으면 adj[i - 97][j - 97] = 0
end loop
end loop
4. 그래프의 전이 폐쇄를 출력한다.
for i = 0부터 노드 수까지
c = 97 + i // 열(세로축) 헤더 준비
end loop
for i = 0부터 노드 수까지
c = 97 + i // 행(가로축) 헤더 출력
for j = 0부터 n_nodes까지
adj[i][j] 출력
end loop
end loop
종료
예제 코드
아래는 위 알고리즘을 C++로 구현한 전체 소스 코드입니다. 프로그램은 먼저 그래프의 노드 개수를 입력받고, 각 노드 쌍 사이에 간선이 존재하는지('y' 또는 'n') 사용자에게 묻습니다. 입력된 정보로 인접 행렬(adjacency matrix)을 구성한 뒤, 이를 전이 폐쇄 행렬 형태로 화면에 출력합니다.
#include<iostream>
using namespace std;
const int n_nodes = 20;
int main() {
int n_nodes, k, n;
char i, j, res, c;
int adj[10][10], path[10][10];
cout << "\n\tMaximum number of nodes in the graph :";
cin >>n;
n_nodes = n;
cout << "\nEnter 'y' for 'YES' and 'n' for 'NO' \n";
for (i = 97; i < 97 + n_nodes; i++)
for (j = 97; j < 97 + n_nodes; j++) {
cout << "\n\tIs there an edge from " << i << " to " << j << " ? ";
cin >>res;
if (res == 'y')
adj[i - 97][j - 97] = 1;
else
adj[i - 97][j - 97] = 0;
}
cout << "\nTransitive Closure of the Graph:\n";
cout << "\n\t\t\t ";
for (i = 0; i < n_nodes; i++) {
c = 97 + i;
cout << c << " ";
}
cout << "\n\n";
for (int i = 0; i < n_nodes; i++) {
c = 97 + i;
cout << "\t\t\t" << c << " ";
for (int j = 0; j < n_nodes; j++)
cout << adj[i][j] << " ";
cout << "\n";
}
return 0;
}
실행 결과
노드 4개(a, b, c, d)로 구성된 그래프에 대해 프로그램을 실행한 결과는 다음과 같습니다. 행렬의 값이 1이면 해당 정점에서 목표 정점으로 도달 가능함을, 0이면 불가능함을 의미합니다.
Maximum number of nodes in the graph :4 Enter 'y' for 'YES' and 'n' for 'NO' Is there an edge from a to a ? y Is there an edge from a to b ?y Is there an edge from a to c ? n Is there an edge from a to d ? n Is there an edge from b to a ? y Is there an edge from b to b ? n Is there an edge from b to c ? y Is there an edge from b to d ? n Is there an edge from c to a ? y Is there an edge from c to b ? n Is there an edge from c to c ? n Is there an edge from c to d ? n Is there an edge from d to a ? y Is there an edge from d to b ? n Is there an edge from d to c ? y Is there an edge from d to d ? n Transitive Closure of the Graph: a b c d a 1 1 0 0 b 1 0 1 0 c 1 0 0 0 d 1 0 1 0
마무리
워셜 알고리즘은 구현이 비교적 간단하면서도 모든 정점 쌍 간의 도달 가능성을 체계적으로 계산할 수 있는 강력한 방법입니다. 시간 복잡도는 O(V³), 공간 복잡도는 O(V²)이므로 정점 수가 수백 개 수준인 그래프까지는 충분히 실용적으로 활용할 수 있습니다. 특히 최단 경로를 구하는 플로이드-워셜(Floyd-Warshall) 알고리즘과 구조가 매우 유사하므로, 두 알고리즘을 함께 학습하면 그래프 이론에 대한 이해를 크게 높일 수 있습니다.