[알고리즘] 강한 연결 요소 추출 알고리즘 (Strongly Connected Component)
강한 연결 요소 (Strongly Connected Component) 방향성이 존재하는 유향 그래프에서 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우 즉, 어떤 두 정점 간의 경로가 존재하면 그 집단이 강하게 연결되었다고 표현합니다. 이것을 강한 연결 요소 혹은 강한 결합 요소라고 말합니다. 또한 전체 그래프가 강한 연결 요소가 아니더라도 전체 그래프의 부분 그래프 안의 정점들이 강한 연결 요소로 묶여있다면 그 부분 그래프는 강한 연결 요소가 됩니다. 이것으로 볼 때, 강한 연결 요소가 성립하는 그래프는 반드시 하나의 유향 사이클을 포함하는 그래프입니다. 알고리즘 원리 깊이 우선 탐색(DFS)을 기반으로 하는 선형 탐색 알고리즘을 사용할 수 있습니다. 코사라주의 알고리즘과 타잔의 알고리즘..
