전이 폐쇄(Transitive Closure)란?
방향 그래프(directed graph)가 주어졌을 때, 그래프의 모든 정점 쌍 (i, j)에 대해 정점 i에서 정점 j가 도달 가능한지(reachable)를 판별할 수 있습니다. 여기서 도달 가능하다는 것은 정점 i에서 시작하여 정점 j에 이르는 경로(path)가 적어도 하나 존재한다는 의미입니다. 이렇게 모든 정점 쌍의 도달 가능성을 행렬 형태로 나타낸 것을 전이 폐쇄(Transitive Closure)라고 합니다.
주어진 그래프 G의 전이 폐쇄를 구하는 데 가장 널리 사용되는 기법은 워셜 알고리즘(Warshall Algorithm)입니다. 아래에서는 이 알고리즘의 동작 과정과 이를 C++로 구현한 예제 코드, 그리고 실제 실행 결과까지 살펴보겠습니다.
알고리즘
Begin
1. 최대 노드 수를 입력받는다.
2. 노드에 a, b, c … 형태로 라벨을 붙인다.
3. 노드 사이에 간선이 존재하는지 검사하기 위해 for 반복문을 구성한다.
// 문자 '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 i = 0 to n_nodes - 1
c = 97 + i
End loop
for i = 0 to n_nodes - 1
c = 97 + i
for j = 0 to n_nodes - 1
Print adj[i][j]
End loop
End loop
EndC++ 예제 코드
#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;
}실행 결과
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
결과 해석 및 참고 사항
위 실행 결과에서 행렬의 값이 1이면 해당 정점 쌍 사이에 간선이 존재함을, 0이면 간선이 없음을 의미합니다. 예를 들어 첫 번째 행의 값 (1, 1, 0, 0)은 정점 a에서 자기 자신과 정점 b로 향하는 간선은 있지만, 정점 c와 d로 가는 직접적인 간선은 없다는 뜻입니다.
참고로, 완전한 전이 폐쇄를 얻으려면 입력받은 인접 행렬을 도달 가능성 행렬로 복사한 뒤, 워셜 알고리즘의 핵심 갱신식인 path[i][j] = path[i][j] || (path[i][k] && path[k][j])를 세 개의 중첩 반복문으로 수행하여 중간 정점을 거쳐 도달 가능한 간접 경로까지 모두 반영해야 합니다. 이 과정의 시간 복잡도는 정점 수를 V라고 할 때 O(V³)입니다.