방향 그래프(directed graph)가 주어졌을 때, 그래프 내 모든 정점 쌍 (i, j)에 대해 정점 j가 정점 i로부터 도달 가능한지(reachable) 판별할 수 있습니다. 여기서 도달 가능하다는 것은 정점 i에서 출발하여 정점 j에 이르는 경로가 하나라도 존재한다는 의미입니다. 이러한 도달 가능 여부를 행렬 형태로 나타낸 것을 그래프의 전이 폐쇄(Transitive Closure)라고 부릅니다.
전이 폐쇄를 구하는 대표적인 방법은 워셜 알고리즘(Warshall Algorithm)입니다. 이 글에서는 워셜 알고리즘의 동작 원리를 단계별로 살펴보고, 이를 C++로 구현한 전체 소스 코드와 실행 결과까지 함께 확인해 보겠습니다.
전이 폐쇄란 무엇인가?
전이 폐쇄 행렬의 각 원소는 다음과 같이 정의됩니다.
- adj[i][j] = 1 : 정점 i에서 정점 j로 가는 경로가 존재함 (직접 연결된 간선 또는 여러 정점을 거친 경로 모두 포함)
- adj[i][j] = 0 : 정점 i에서 정점 j로 갈 수 있는 경로가 전혀 없음
일반적인 인접 행렬은 두 정점 사이에 간선이 직접 존재하는지만 알려주지만, 전이 폐쇄는 다른 정점을 경유하여 도달 가능한지까지 모두 포함한다는 점이 핵심 차이입니다.
알고리즘
- 그래프의 최대 노드 수를 입력받습니다.
- 노드를 a, b, c, … 순서로 라벨링합니다.
- 모든 정점 쌍에 대해 간선 존재 여부를 입력받아 인접 행렬(adj)을 구성합니다.
- 워셜 알고리즘을 적용하여 전이 폐쇄를 계산합니다.
- 계산된 전이 폐쇄 행렬을 화면에 출력합니다.
Begin
1. 최대 노드 수(n_nodes)를 입력받는다.
2. 노드를 a, b, c, ... 로 라벨링한다.
3. 노드 간 간선 존재 여부를 확인하기 위해 반복문을 사용한다.
// 문자 'a'의 ASCII 코드는 97
for i = 97 to (97 + n_nodes)-1
for j = 97 to (97 + n_nodes)-1
간선이 존재하면
adj[i - 97][j - 97] = 1
아니면
adj[i - 97][j - 97] = 0
End loop
End loop
4. 워셜 알고리즘으로 전이 폐쇄를 계산한다.
for k = 0 to n_nodes-1
for i = 0 to n_nodes-1
for j = 0 to n_nodes-1
adj[i][j] = adj[i][j] OR (adj[i][k] AND adj[k][j])
End loop
End loop
End loop
5. 그래프의 전이 폐쇄를 출력한다.
for i = 0 to n_nodes-1
c = 97 + i // 행 라벨 출력
for j = 0 to n_nodes-1
adj[i][j] 값 출력
End loop
End loop
End
워셜 알고리즘의 핵심 아이디어는 ‘정점 k를 경유지로 사용할 때 i에서 j로 갈 수 있는가?’를 모든 k에 대해 검사하는 것입니다. 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
const int MAX_NODES = 10;
int main() {
int n_nodes;
char res, c;
int adj[MAX_NODES][MAX_NODES];
cout << "\n\t그래프의 최대 노드 수 : ";
cin >> n_nodes;
cout << "\n간선이 있으면 'y', 없으면 'n'을 입력하세요\n";
for (char i = 'a'; i < 'a' + n_nodes; i++) {
for (char j = 'a'; j < 'a' + n_nodes; j++) {
cout << "\n\t정점 " << i << "에서 " << j << "(으)로 가는 간선이 있습니까? ";
cin >> res;
adj[i - 97][j - 97] = (res == 'y') ? 1 : 0;
}
}
// 워셜 알고리즘: 전이 폐쇄 계산
for (int k = 0; k < n_nodes; k++)
for (int i = 0; i < n_nodes; i++)
for (int j = 0; j < n_nodes; j++)
adj[i][j] = adj[i][j] | (adj[i][k] & adj[k][j]);
cout << "\n\n그래프의 전이 폐쇄:\n";
cout << "\n\t\t ";
for (int 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" << c << " ";
for (int j = 0; j < n_nodes; j++)
cout << adj[i][j] << " ";
cout << "\n";
}
return 0;
}
실행 결과
그래프의 최대 노드 수 :4 간선이 있으면 'y', 없으면 'n'을 입력하세요 정점 a에서 a(으)로 가는 간선이 있습니까? y 정점 a에서 b(으)로 가는 간선이 있습니까? y 정점 a에서 c(으)로 가는 간선이 있습니까? n 정점 a에서 d(으)로 가는 간선이 있습니까? n 정점 b에서 a(으)로 가는 간선이 있습니까? y 정점 b에서 b(으)로 가는 간선이 있습니까? n 정점 b에서 c(으)로 가는 간선이 있습니까? y 정점 b에서 d(으)로 가는 간선이 있습니까? n 정점 c에서 a(으)로 가는 간선이 있습니까? y 정점 c에서 b(으)로 가는 간선이 있습니까? n 정점 c에서 c(으)로 가는 간선이 있습니까? n 정점 c에서 d(으)로 가는 간선이 있습니까? n 정점 d에서 a(으)로 가는 간선이 있습니까? y 정점 d에서 b(으)로 가는 간선이 있습니까? n 정점 d에서 c(으)로 가는 간선이 있습니까? y 정점 d에서 d(으)로 가는 간선이 있습니까? n 그래프의 전이 폐쇄: a b c d a 1 1 1 0 b 1 1 1 0 c 1 1 1 0 d 1 1 1 0
결과 해석
입력된 간선 정보를 보면 a→b→c, c→a처럼 여러 정점을 거치는 경로가 존재합니다. 따라서 인접 행렬에서는 0이었던 a→c 같은 항목도 전이 폐쇄에서는 1로 바뀝니다. 위 결과는 ‘a, b, c, d 어느 정점에서 출발하더라도 a, b, c에는 도달할 수 있지만, 어떤 정점에서도 d로는 직접적·간접적으로 도달할 수 없다’는 사실을 명확하게 보여줍니다.
이처럼 워셜 알고리즘을 활용하면 그래프의 전체적인 도달 가능성 구조를 손쉽게 파악할 수 있으며, 네트워크 라우팅, 데이터베이스 관계 분석 등 다양한 분야에서 유용하게 응용됩니다.