강한 연결 요소는 방향 그래프에서 서로 왕복 도달 가능한 정점들의 최대 집합이다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
원리
두 정점이 같은 요소에 속하려면 양방향 도달성이 필요하다. 각 요소를 하나의 정점으로 압축하면 요소 사이의 그래프는 방향 비순환 그래프가 된다.
예시
A→B→C→A가 있고 C→D만 있다면 A, B, C는 한 요소가 되지만 D는 별도 요소다. D에서 돌아오는 경로가 없기 때문이다.
주의할 점
단순히 간선이 이어져 있다는 약한 연결성과 구별한다. 코사라주와 타잔 알고리즘이 대표적이며 방문 순서와 스택 상태를 정확히 관리해야 한다.