Strongly Connected Component

개념

요소(Component)는 알겠는데.... 강하게 연결 (Strongly Connected) 되었다는게 뭘까요?

강하게 연결되었다는 뜻은 방향이 있는 그래프에서 집단 안에 있는 모든 정점이 다른 모든 정점에 도달할 수 있는 경우를 이야기합니다.

좀 말이 어렵죠? 아래 그래프를 통해 조금 더 자세히 알아보겠습니다.

위 그래프에서 정점 a, b, c에 집중해주세요.

• 정점 a는 b로, c로, 그리고 a로 도달할 수 있네요.
• 정점 b는 c로, a로, 그리고 b로 도달할 수 있네요.
• 정점 c는 a로, b로, 그리고 c로 도달할 수 있네요.

이렇게 집단 안에 있는 요소 { a, b, c }에 대해 모든 정점이 다른 모든 정점에 도달할 수 있는 경우를 이야기합니다.

개념은 얼추 알겠어. 그래서 어떻게 구해?

SCC를 구하는 방법으로는 타잔 알고리즘과 코사라주 알고리즘이 있습니다.

위 링크를 통해 확인해주세요. (코사라주 알고리즘은 아직 미작성하였습니다.)