이번에는 강 연결 성분을 찾는 알고리즘 중 역방향 그래프를 활용하는 Kosaraju 알고리즘에 대해서 알아보겠습니다. Kosaraju 알고리즘 Kosaraju 알고리즘은 이전 글에서도 잠깐 설명했지만, 역방향 그래프를 통해서 구현합니다. 해당 과정을 그림과 함께 확인해봅시다. 위와 같은 그래프가 있습니다. 가장 먼저 우리는 위상 정렬을 통해서 해당 그래프를 선형으로 정렬하겠습니다. 위상정렬은 어떻게 하냐에 따라 결과라 다르지만, 우리는 3번 정점부터 탐색하기 시작하여 [4, 7, 1, 0, 6, 5, 3, 2, 9, 8]로 정렬했다고 해봅시다. 그럼 이제, 이 위상 정렬을 역순을 취해줍니다. [8, 9, 2, 3, 5, 6, 0, 1, 7, 4] 그럼 해당 정렬은 위상 정렬의 역순이 되고, 이는 그림 1..
