Directed Acyclic Graph
-
[Algorithm] How To Find SCC in Linear Time Complexity?알고리즘 2022. 11. 15. 21:50
Undirected Graph에서는 Connected Component를 구하려면 아무 Vertex나 잡고 DFS를 수행한 결과 생성되는 DFS Tree 가 Connected Component 였다. (Definition of Connected Component of Graph G : G의 maximal 한 connected subgraph) Directed Graph에서는 Connected를 Strongly Connected로 정의하는 것이 일반적이다. 그럼 Strongly Connected란 무엇일까? Definition of Strongly Connected in Directed Graph Directed Graph G에서 G에 속한 서로 다른 두 vertex v, u에 대하여 path v to u..