19. SCC
Strongly Connected Component, 강한 결합 요소
graph안에서 강하게 결합이 이루어진 정점들의 집합을 일컫는데, 쉽게 말하면 사이클(부모노드와 자식노드가 서로에게 도달이 가능한 상태)이 가능한 정점들을 SCC에 속한다고 한다.
SCC는 방향이 있는 그래프에서 사이클이 발생하는 경우에 의미가 있고, 무향그래프와 같이 별도의 방향이 설정되어있지 않다면 의미가 크게 없다.
19-1. SCC 탐색 알고리즘
SCC를 탐색하는 알고리즘은 결과적으로 SCC 결과를 추출하는 알고리즘이다.
이 알고리즘은 코사라주와 타잔 방법이 있다.
- 코사라주는 구현이 쉽다는 장점
- 타잔은 적용이 쉽다는 장점
19-2. 타잔알고리즘(대략적인 과정)
타잔 알고리즘은 모든 정점에 대해 DFS를 수행하면서 SCC를 찾는 알고리즘이다.
위 그래프에서 SCC 관계에 있는 노드집합은 4개가 존재한다.
- 1/2/3
- 4
- 5/6/7
- 8/9/10/11
첫번째 집합에 대해 살펴보도록 하자.
- 부모노드를 1로 설정하고 DFS를 진행한다.
- stack에 최초 부모노드인 1을 저장한다.
- 그 후 인접노드인 2와 3을 stack에 넣는다.
- 이때 3은 1의 DFS가 종료되지 않은 시점에서 부모노드가 1임을 확인된다.
- 마찬가지로 2역시 1의 DFS가 종료되지 않은 시점에서 부모노드가 1임을 확인된다.
- 2,3을 제거하고 1까지 모두 제거하면 하나의 부모노드를 가지는 노드집합이 추출된다.
최종적으로 추출된 노드집합인 1,2,3이 SCC이다.
SCC의 종료시점은 부모노드의 DFS 종료시점, 즉 DFS를 수행하면서 자기자신이 나올때까지이다.
19-3. SCC의 활용
즉 각 노드들을 DFS를 수행하면서 부모값이 갱신되고, 갱신된 부모값을 비교하면서 SCC요소를 찾는다.
각 SCC그룹을 묶고, 그룹에 대한 위상정렬을 수행하는 경우가 존재하는데 이럴때 위 SCC(타잔)알고리즘을 활용한다.
19-4. 세부 알고리즘
실제 알고리즘을 구현하기 위해선 각 노드에 id값을 저장하고, DFS가 완료된 노드를 저장하는 배열이 각각 필요하다.
**추가공부필요
알고리즘 구현방법을 더 고민해보고 올릴 것!
