•
개요
◦
강한 결합 요소란 그래프 안에서 강하게 결합된 정점 집합을 의미한다.
◦
서로 긴밀하게 연결되어 있다고 하여 강한 결합 요소라고 한다. SCC는 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다는 특징이 있다.
◦
사이클이 발생하는 경우 무조건 SCC에 속한다. 무향 그래프라면 그 그래프 전체는 무조건 SCC이므로 방향 그래피을때만 의미가 있다.
•
알고리즘
◦
SCC를 추출하는 대표적인 알고리즘은 코사라주 알고리즘과 타잔 알고리즘이 있다.
◦
타잔 알고리즘
▪
모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘이다.
▪
