Transitive Closure: 도달 가능성 폐포

Transitive Closure, 이행 폐포, reachability closure

정의

Transitive Closure 는 그래프의 모든 (u, v) 쌍에 대해 u 에서 v 로 도달 가능한지 담은 부울 행렬입니다.

Floyd-Warshall 변형

vector<vector<bool>> reach(n, vector<bool>(n));
for (int u = 0; u < n; u++) reach[u][u] = true;
for (auto [u, v] : edges) reach[u][v] = true;

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

O(V³). 비트셋으로 최적화 시 O(V³/64) 실전 유리.

DFS/BFS 반복

각 정점 s 마다 도달 가능한 정점 표시. O(V(V+E)). Sparse graph 에서 유리.

응용

• DAG 축약 후 이행 폐포
• 관계 추론 (family tree, dependency)

참고

• Floyd-Warshall
• Tarjan SCC (사이클 축약 후)