[알고리즘] Graph (3) - Strongly connected components(SCC)
[3. Strongly connected conponents] 1. 방향그래프의 연결관계 connected → 방향 그래프에서 노드 v와 노드 u가 서로에게 도달할 수 있는 경로가 존재할 때, 두 노드는 연결되어 있는 상태 2. SCC 집합 → 개체들을 상호 연결 관계에 따라 개체끼리 집합으로 분류 → SCC내의 모든 노드들은 서로 도달할 수 있음 → 위 그래프의 SCC : {A}, {B, E}, {C, F}, {D}, {G, H, I, J, K, L} 3. SCC의 성질 (1) SCC로 만든 방향그래프는 dag이다. (2) 깊이우선탐색에서 가장 높은 post number를 갖는 노드는 SCC로 만든 그래프의 source에 위치해야 한다. (3) SCC인 C와 C'가 있을 때 C에서 C'로 향하는 간선이..
2022. 11. 29.