목록2025/05/13 (1)
Elevation
그래프 (6) - 강한 연결 요소
강한 연결 요소(Strongly Connected Component, SCC)를 구하는 알고리즘에 대해 알아보자. scc란 방향 그래프에서 정의되는 정점들의 최대 부분집합인데, 집합 안의 임의의 두 정점 $u, v$에 대해 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재해야 한다. 쉽게 생각해서, 임의의 한 점에서 다른 점으로 자유롭게 이동 가능한 점들의 최대 그룹이라고 생각하면 된다. scc를 구하는 방법에는 코사라주(kosaraju) 알고리즘과 타잔(tarjan) 알고리즘이 있다. 두 방법 모두 dfs를 이용하기 때문에 시간복잡도는 $O(V+E)$가 된다. 코사라주 알고리즘코사라주 알고리즘은 다음과 같이 dfs를 2번 진행하여 scc를 구한다. 한 점에서부터 dfs를 진행..
ps/graph
2025. 5. 13. 00:56