강한 연결 요소 (Strongly Connected Component)

이번에 제가 설명할 주제는 강한 연결 요소 (Strongly Connected Component)입니다. 유향그래프에서, 어느 한 정점에서 출발하여 다시 자신으로 돌아오는 경로를 사이클이라고 합니다. 위의 그림은 사이클이 존재하는 유향그래프를 나타냅니다. 

유향그래프에서 하나의 사이클은 내부적으로 하나 이상의 서브사이클이 존재할 수 있습니다. 그림과 같이 유향그래프에서 A->B->D->C->A의 사이클 내에 A->B->C->A와 B->D->C->B와 같은 서브사이클이 존재하는 것을 알 수 있습니다. 여기서, 한 정점을 지나는 모든 사이클 중에서 가장 많은 정점을 포함하는 사이클의 정점들의 집합을 강한 연결 요소 (Strongly Connected Component)라고 합니다. 그림의 예시에서는 A->B->D->C->A의 사이클에 포함된 정점 A, B, C, D이 같은 강한 연결 요소 (줄여서 SCC)에 포함됩니다. 그러면 유향그래프에서 모든 SCC를 구하는 알고리즘을 설명드리겠습니다.

위키피디아에 게시된 유향그래프 예시를 보면 이미 같은 SCC를 기준으로 영역이 표시된 것을 알 수 있습니다. 즉, {a, b, e}, {f,g} 그리고 {c,d,h}는 각각의 SCC를 나타냅니다. SCC를 계산하기 위해, 우리는 우선 사이클을 찾는 방법부터 알아야 합니다. 앞서 설명드린 것과 같이, 사이클은 한 정점에서 출발하여 다시 자신으로 돌아오는 경로를 말합니다. 다른 말로, 어느 한 정점을 기준으로 자식 정점들이 자기자신으로 돌아오는 경로가 존재하면서, 자신의 부모정점으로 가는 경로가 존재하지 않는다는 것을 확신할 수 있을 때, SCC를 만들 수 있습니다. 

사이클을 계산하기 위해 한 정점부터 탐색을 시작할 때, 우리는 임의의 정점 i가 정점 j보다 부모인지 자식인지 파악하기 위해 방문한 정점마다 순번을 부여할 수 있습니다. 즉, 첫 번째 방문한 정점은 0, 두 번째 방문한 정점은 1 ,…, n번째 방문한 정점은 n-1과 같이 번호를 부여한 후에 자신이 방문할 정점에 번호가 존재한다면, 해당 정점은 적어도 자신보다 부모정점이라고 할 수 있습니다. 예를 들어, 위와 같은 그래프가 존재하는 상황에서, 깊이우선탐색(DFS) 방법으로 정점 A부터 탐색을 시작할 경우의 설명을 드리겠습니다.

정점 A의 유일한 자식정점 B를 방문합니다. 

정점 B에서는 C, D, E의 자식정점이 있는데 알파벳 순으로 C를 먼저 방문합니다. 

정점 C는 A와 B를 자식으로 갖지만, 두 정점은 이미 방문했기 때문에 재방문을 하지 않습니다. 단, 우리는 SCC를 구하기 위해 두 정점 중에서 순번이 더 적은, 즉, 가장 부모가 되는 정점의 번호인 1을 B에게 반환합니다. 

정점 B는 다음 자식인 정점 D로 방문을 하고 D는 이미 방문한 정점 C를 방문하지 않고 C의 순번 3을 B에게 반환합니다. 

마지막으로 정점 B는 E를 방문하고, E는 다시 자식 정점 F를 방문합니다. 

F는 더 이상 새롭게 방문할 정점이 없기 때문에 정점 E의 번호 5를 E를 에게 반환합니다.

E는 더 이상 방문한 자식 정점이 없으면서 F로부터 반환받은 번호가 자신의 번호와 일치하기 때문에 E를 기준으로 SCC를 만들 수 있는 조건을 충족합니다. 따라서, 가장 최근에 방문한 정점들 중에서 E 이후의 정점들을 하나의 SCC로 묶을 수 있습니다. 즉, 가장 마지막에 방문한 정점부터 정점 E까지 추출하면 되는데, 이를 위해 가장 효율적인 방법이 자료구조 스택을 사용하여 방문한 정점들을 스택에 순서대로 추가했다가, SCC를 생성하는 순간에 순차적으로 추출할 수 있습니다. 오른쪽 그림과 같이 정점 F까지 방문했을 때 스택에 정점들이 순서대로 저장된 것을 알 수 있습니다. 

스택에서 추출한 E와 F에 대해 SCC 그룹을 생성합니다. 다음으로, B는 C, D, E로부터 반환받은 번호 1, 3, 5 중에서 가장 작은 값 1을 A에게 반환합니다. A에서 번호 1이 자신의 번호와 일치하기 때문에 마찬가지로 스택에서 A가 나올 때 까지 정점들을 추출하여 이들을 하나의 SCC 그룹으로 생성합니다.

이로써 하나의 그래프에 대해 깊이우선탐색을 이용하여 모든 SCC를 구하는 과정에 대해 설명드렸습니다. 깊이우선탐색을 사용하면 스택에서 한 정점 A 이후의 추가된 정점들은 모두 정점 A의 자식이라는 것을 확신할 수 있습니다. 그러나, 너비우선탐색을 사용하면 그것을 확신할 수 없습니다. 따라서, SCC를 만들 수 있는 조건을 충족하더라도 해당 정점의 자식정점들 중에서 자신으로 돌아오는 경로에 포함된 정점들이 다시 계산해야하는 문제가 발생하게 됩니다. 따라서, SCC를 계산할 때는 깊이우선탐색과 스택을 사용하는 것이 효율적이라 할 수 있습니다.