강한 연결 요소
pre visit 과 post visit
DFS 를 하며 버텍스 별로 계산할 수 있는 수가 있다.
previsit number와 postvisit number 가 그것이다.
previsit number 는 처음 방문한 순서이다.
postvisit number 는 마지막으로 방문한 순서이다.
dfs 는 재귀함수이고, 저 깊이 갔다가 돌아오는 방법이기 때문에 이 수의 측정이 가능하다.
위 이미지의 왼쪽 그래프를 오름차순으로 DFS 를 진행했을 때
오른쪽과 같은 DFS 스패닝 트리가 그려지며
왼쪽 수는 previsit, 오른쪽이 postvisit이다.
이를 구현하는 방법은 쉽다.
먼저 전역변수로 previsit, postvisit 의 배열을 버텍스 수만큼 만들어주고
0으로 초기화 된 정수 cnt 하나 선언한 후
dfs 함수의 위에서 previsit에 cnt를 1씩 증가시키고 저장해나가고
함수의 마지막에 postvisit 에 cnt를 1씩 증가시키고 저장하면 된다.
DFS Spanning Tree
이미지의 오른쪽의 트리는 DFS 스패닝 트리라고 하는데
이는 DFS 했을 때 실제로 지나는 엣지만을 그린 트리이다.
점선은 DFS 에서는 쓰이지는 않지만 그래프에 존재는 하는 엣지이다.
그 중 위로, 즉 트리에서의 자기의 부모로 올라가는 엣지를 Back Edge,
자신의 아이로 내려가는 엣지를 Forward Edge,
둘 다 아니면 Cross Edge 이다.
나머지 굵은 선을 Tree Edge 라고 한다.
Directed Acyclic Graph (DAG)
방향이 존재하는 그래프에서는
사이클이 생길 수가 있다.
이때 우리는 사이클이 없는 그래프를 다루려고 한다.
사이클이 없는 그래프는
source 와 sink 버텍스라는 것을 가진다.
source 는 엣지가 항상 바깥을 향하는 버텍스이고
sink 는 엣지가 항상 자신을 향하게 하는 버텍스이다.
DAG 의 성질
한 버텍스에서 다른 버텍스에서 가는 경로가
선형적이고 위상적인 순서를 가지게 된다.
돌아오는 길이 없이 경로의 앞에 있는 버텍스는 뒤의 버텍스보다 일찍 방문되는 것이다.
방향 있는 그래프는 DFS 를 했을 때 back edge 가 있어야지만 사이클을 가진다.
DAG 에서는 가는 방향에 있는 그래프는 항상 이전보다 낮은 post number 를 가진다.
모든 DAG는 최소 하나의 source 와 하나의 sink 를 가지고 있다.
이를 통하여 강한 연결 요소를 찾아보자.
강한 연결 요소
u에서 v로, v에서 u로 가는 길이 있으면
이 둘은 연결되었다고 한다.
그리고 그 ‘연결됨’의 정의에 따라
버텍스를 각각 겹치지 않는 집합으로 나눈다.
DAG의 성질과 post number 를 이용
이를 찾는 알고리즘은 다음의 성질을 이용한다.
-
만약 dfs 가 노드(버텍스) u 에서 시작했다면,
u 가 방문할 수 있는 노드를 다 방문하자마자 그 함수는 끝난다. -
가장 높은 post number 가 부여되는 노드는 강한 연결 요소에서 source 에 위치한다.
(이는 당연한 말로, post number 가 가장 높다는 말은 그 노드에서 방문을 시작해 모든 노드를 탐색 후 그 노드로 돌아온다는 말이다. ) -
만약 노드 C와 C’이 강한 연결 요소라면 C에서 C’로 가는 엣지가 있고,
이때 C 에서 가장 큰 post number 는 C’에서의 그것보다 크다.
이에 따라 다음과 같은 전략을 세울 수 있다.
sink 가 되는 강한 연결 요소를 찾아 제거하는 동작을
단 하나의 강한 연결 요소가 남을 때까지 이를 반복한다.
알고리즘
강한 연결 요소를 어떻게 찾을 것인가?
역방향 그래프의 source 는 원래 그래프의 sink 이다.
역방향 그래프에서 dfs 를 하며 post number 를 조사하면 (성질 1)
거기서 가장 큰 수를 갖는 것이 source 이므로 (성질 2)
이는 원래 그래프에서의 sink 에 해당한다.
그 노드부터 원래 그래프에서 DFS 를 하면
전부 탐색을 하지 못하고 일부분에서 그칠 것이다. (sink 는 source 로 가지 못함)
그리고 다음으로 큰 post number 에 해당하는 노드를 선택해서
또 dfs를 하면 그 다음 강한 연결요소가 나올 것이고,
그 둘은 단방향으로 연결되어 있다. (성질 3)
참고로, 가장 큰 post number 를 구하기 위해 이를 정렬할 필요가 없다.
왜냐하면 어차피 post number 는 작은 순서대로 계산이 되므로 (성질 1)
스택에 저장할 시 위에 있을 수록 크다.
시간복잡도
DFS 두 번이면 끝난다.
DFS 의 시간복잡도 O(n + m) 과 같다.