Strongly Connected Component
SCC는 강한연결요소라고 합니다.
SCC는 방향그래프에서의 노드들의 부분집합으로, 한 SCC에 속하는 노드들끼리는 사이클이 존재합니다.
한 SCC에 속하는 임의의 두 노드 u, v에 대해 u에서 v로의 경로와, v에서 u로의 경로가 존재합니다.
모든 노드는 최소한 자기자신이 SCC에 속합니다.
stack으로 위상정렬
그래프를 DFS 하면서 현재 노드에서 연결된 모든 노드를 방문한 후 마지막에 현재 노드를 스택에 저장하면,
스택에는 그래프의 위상정렬의 역순으로 저장되어 있습니다.
역방향 그래프
원래 그래프의 모든 엣지의 방향을 반대로 한 그래프를 역방향 그래프라고 합니다.
원 그래프의 위상정렬의 역순으로 역방향 그래프를 방문하면 SCC의 원소들을 방문하게 됩니다.
구현
'알고리즘 > 그래프' 카테고리의 다른 글
| [그래프 알고리즘]오일러 경로/회로 Eulerian Path/Circuit(방향 그래프) (0) | 2022.07.12 |
|---|---|
| [그래프 알고리즘]오일러 경로/회로 Eulerian path/circuit(무향그래프) (0) | 2022.07.12 |
| [그래프 알고리즘]Tarjan 알고리즘(SCC) (0) | 2022.07.11 |
| [그래프 알고리즘]boruvka 알고리즘(MST) (0) | 2022.07.11 |
| [그래프 알고리즘]kruskal 알고리즘(MST) (0) | 2022.07.11 |