Kosaraju's Algorithm (1) 썸네일형 리스트형 131. Kosaraju's Algorithm 먼저 임의의 정점 $v$가 주어졌을 때 $v$를 포함하는 SCC 하나를 구하는 방법을 살펴본다. $v$에서 이동할 수 있는 정점들과 $v$로 이동할 수 있는 정점들의 교집합을 구하면 그 집합에 속한 정점들이 한 SCC로 묶이게 된다. $v$에서 이동할 수 있는 정점들은 DFS로 쉽게 구할 수 있고, $v$로 이동할 수 있는 정점들은 간선들을 전부 뒤집은 다음 DFS를 실행하면 구할 수 있다. 두 번의 DFS에서 모두 방문한 정점들은 $v$와 같은 SCC에 속한다. 따라서 다음과 같은 방법으로 그래프의 SCC를 전부 구할 수 있다. (그래프에 존재하는 정점의 수가 $n$이라고 가정한다.) 1. 아직 SCC로 묶이지 않은 정점 중 하나를 선택해서 그 정점에서 DFS를 실행한다. 2. 그래프의 간선을 전부 뒤.. 이전 1 다음
