그래프 이론에서 전이 폐쇄(Transitive Closure)란 한 정점 u에서 다른 정점 v로 도달할 수 있는지를 나타내는 도달 가능성 행렬(reachability matrix)입니다. 하나의 그래프가 주어졌을 때, 모든 정점 쌍 (u, v)에 대해 v가 u로부터 도달 가능한지 여부를 구하는 것이 목표입니다.
전이 폐쇄 행렬의 특징
최종 결과 행렬은 부울(Boolean) 타입으로 구성됩니다. 정점 u에서 정점 v로 가는 값이 1이라면, u에서 v로 이어지는 경로가 최소 하나 이상 존재한다는 의미입니다. 반대로 값이 0이면 어떤 경로를 통해서도 도달할 수 없음을 나타냅니다.
입력 및 출력 예시
아래 예시에서 입력은 그래프의 인접 행렬이며, 출력은 해당 그래프의 전이 폐쇄 행렬입니다.
Input: 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 Output: The matrix of transitive closure 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1
알고리즘
전이 폐쇄는 플로이드-워셜(Floyd-Warshall) 알고리즘과 유사한 방식으로 구할 수 있습니다. 먼저 인접 행렬을 결과 행렬에 복사한 뒤, 모든 정점 k를 '경유 정점'으로 고려하면서 행렬을 갱신합니다. 만약 i에서 k로 갈 수 있고, k에서 j로 갈 수 있다면 i에서 j로도 도달 가능하다고 표시하는 원리입니다.
transClosure(graph)
입력: 주어진 그래프
출력: 전이 폐쇄 행렬
Begin
copy the adjacency matrix into another matrix named transMat
for any vertex k in the graph, do
for each vertex i in the graph, do
for each vertex j in the graph, do
transMat[i, j] := transMat[i, j] OR (transMat[i, k] AND transMat[k, j])
done
done
done
Display the transMat
End
C++ 구현 예제
다음은 위 알고리즘을 C++로 구현한 코드입니다. 4개의 정점을 가진 방향 그래프를 대상으로 전이 폐쇄 행렬을 계산하고 출력합니다.
#include<iostream>
#include<vector>
#define NODE 4
using namespace std;
int graph[NODE][NODE] = {
{1, 1, 0, 1},
{0, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1}
};
int result[NODE][NODE];
void transClosure() {
for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++)
result[i][j] = graph[i][j]; // 처음에는 그래프를 결과 행렬에 복사
for(int k = 0; k<NODE; k++)
for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++)
result[i][j] = result[i][j] || (result[i][k] && result[k][j]);
for(int i = 0; i<NODE; i++) { // 결과 행렬 출력
for(int j = 0; j<NODE; j++)
cout << result[i][j] << " ";
cout << endl;
}
}
int main() {
transClosure();
}
실행 결과
1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1
시간 복잡도 분석
이 알고리즘은 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(V³)입니다. 여기서 V는 그래프의 정점 수입니다. 또한 결과 행렬을 저장하기 위해 O(V²)의 공간이 필요합니다. 정점 수가 많아지면 연산량이 급격히 늘어나므로, 대규모 그래프에서는 DFS나 BFS를 각 정점에서 수행하여 도달 가능성을 구하는 방법도 고려할 수 있습니다.