flowchart TD
Init["초기: 직접 간선만 TC에 포함"]
K0["k=0: 0을 경유한 경로 추가"]
K1["k=1: 1을 경유한 경로 추가 (TC[0][2] = 1)"]
K2["k=2: 2를 경유한 경로 추가 (TC[1][3] = 1)"]
K3["k=3: 3을 경유한 경로 추가"]
Done["완성: V x V 도달 가능성 행렬"]
Init --> K0 --> K1 --> K2 --> K3 --> Done
k=1 처리 후: TC[0][1]=1, TC[1][2]=1 이므로 TC[0][2] = 1 추가.
k=2 처리 후: TC[1][2]=1, TC[2][3]=1 이므로 TC[1][3] = 1 추가.
핵심 아이디어
Floyd-Warshall 변형
최단 경로 대신 도달 가능성을 다루도록 변환. 핵심 점화식:
TC[i][j]=TC[i][j]∨(TC[i][k]∧TC[k][j])
“i에서 k로, 그리고 k에서 j로 갈 수 있으면 i에서 j로 갈 수 있다.”
# Floyd-Warshall TC 초기화for u in 0..V-1: TC[u][u] = truefor (u, v) in edges: TC[u][v] = true# 경유 정점 k 순서로 갱신for k in 0..V-1: for i in 0..V-1: for j in 0..V-1: TC[i][j] = TC[i][j] OR (TC[i][k] AND TC[k][j])
최적화: if TC[i][k] 체크로 내부 루프 스킵 가능.
DFS/BFS per Source
모든 정점 s에서 BFS/DFS를 실행해 도달 가능한 정점을 표시. O(V(V+E)). Sparse 그래프에서 Floyd-Warshall 보다 유리.
for s in 0..V-1: TC[s][s] = true BFS/DFS from s: TC[s][v] = true for each visited v
Bitset 최적화
TC의 각 행을 bitset으로 표현하면 OR 연산이 64비트 단위로 처리됩니다.
시간:O(V{3}64),V=104이상에서실전유리
C++ bitset<V> 배열: 각 TC[i] |= TC[k] 가 비트셋 OR 연산 하나.
알고리즘
Floyd-Warshall TC (Dense, V <= 5000)
TC[i][j] = 직접 간선 + 대각선for k = 0..V-1: for i = 0..V-1: if not TC[i][k]: continue # 최적화 TC[i] |= TC[k] # 비트셋 가정 시 한 줄
BFS per Source (Sparse, V 크고 E 작을 때)
for s = 0..V-1: queue = {s}, visited = {s} while queue not empty: u = pop(queue) TC[s][u] = true for v in adj[u]: if not TC[s][v]: TC[s][v] = true push(queue, v)
DAG 최적화: 위상 정렬 역순
DAG라면 위상 정렬 역순으로 처리해 각 정점에서 후계 정점들의 TC를 OR 합산. O(V+E) 전처리 + O(V) OR 합산.
구현
// Transitive Closure: Floyd-Warshall + Bitset 최적화#include <bits/stdc++.h>using namespace std;// 방법 1: Floyd-Warshall (O(V^3))vector<vector<bool>> tc_floyd(int V, vector<pair<int,int>>& edges) { vector<vector<bool>> tc(V, vector<bool>(V, false)); for (int u = 0; u < V; u++) tc[u][u] = true; for (auto [u, v] : edges) tc[u][v] = true; for (int k = 0; k < V; k++) for (int i = 0; i < V; i++) if (tc[i][k]) for (int j = 0; j < V; j++) tc[i][j] = tc[i][j] || tc[k][j]; return tc;}// 방법 2: BFS per Source (O(V(V+E)), Sparse 유리)vector<vector<bool>> tc_bfs(int V, vector<vector<int>>& adj) { vector<vector<bool>> tc(V, vector<bool>(V, false)); for (int s = 0; s < V; s++) { tc[s][s] = true; queue<int> q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!tc[s][v]) { tc[s][v] = true; q.push(v); } } } } return tc;}int main() { int V = 4; vector<pair<int,int>> edges = {{0,1},{1,2},{2,3},{0,3}}; vector<vector<int>> adj(V); for (auto [u, v] : edges) adj[u].push_back(v); auto tc1 = tc_floyd(V, edges); cout << "Floyd-Warshall TC:\n"; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) cout << tc1[i][j] << " "; cout << "\n"; } auto tc2 = tc_bfs(V, adj); cout << "BFS TC:\n"; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) cout << tc2[i][j] << " "; cout << "\n"; } return 0;}
from collections import dequedef tc_floyd(n, edges): """Floyd-Warshall Transitive Closure O(V^3)""" tc = [[False]*n for _ in range(n)] for u in range(n): tc[u][u] = True for u, v in edges: tc[u][v] = True for k in range(n): for i in range(n): if tc[i][k]: for j in range(n): if tc[k][j]: tc[i][j] = True return tcdef tc_bfs(n, edges): """BFS per Source O(V(V+E)), Sparse 그래프 유리""" adj = [[] for _ in range(n)] for u, v in edges: adj[u].append(v) tc = [[False]*n for _ in range(n)] for s in range(n): tc[s][s] = True q = deque([s]) while q: u = q.popleft() for v in adj[u]: if not tc[s][v]: tc[s][v] = True q.append(v) return tcdef print_tc(tc, label): print(f"{label}:") for row in tc: print(" ".join("1" if x else "0" for x in row))n = 4edges = [(0,1),(1,2),(2,3),(0,3)]print_tc(tc_floyd(n, edges), "Floyd-Warshall TC")print_tc(tc_bfs(n, edges), "BFS TC")
💬 댓글