2021.07.04
코사라주 알고리즘(Kosaraju's Algorithm)
코사라주 알고리즘(Kosaraju's Algorithm) 그래프에서 강한 연결 요소를 찾는 가장 쉽고 널리 사용되는 방법 DFS를 2번 수행하는 형태로 동작함. ① 입력 그래프 자체에 DFS를 수행함. ② 입력 그래프를 전치하여 DFS를 수행함. 코사라주 알고리즘은 일반적으로 DFS 방식 의 순회를 사용하지만, BFS 도 사용할 수 있음. DFS 방식이 전통적인 방식 복잡할 수 있는 문제를 직관적으로 단순화하는 측면에서 매우 효과적이며, 구현하기도 쉬운 편임. 입력 그래프가 인접 리스트 로 표현되어 있을 경우, O(V + E) 형태의 선형 점근적 시간 복잡도 를 갖기 떄문에 매우 효율적임. 코사라주 알고리즘에서 인접 행렬 을 사용하는 것은 권장되지 않음. 그래프 순회에서 각 정점의 이웃을 찾기 위해 상당..
