그래프에서 SCC (Strongly Connected Component) 찾기

SCC에 대한 증명을 위한 글이 아님을 알려드립니다!

 

 SCC란 그래프에서 서로 다른 노드 u, v 2개를 뽑았을때, u->v로도 직간접적으로 갈 수 있고, v->u로도 역시 직간접적으로 갈 수 있는 노드들의 집합이다.

 

위의 그림에서 SCC를 추출해보자면, [1, 2, 3], [4, 5], [6] 으로 나뉠 것이다.

사람의 눈으로 직관적인 분리는 쉽지만, 이를 코드로 구현할 때를 생각해보자

 

 

 

그런데! SCC를 찾기 아주 조금 전에 우선적으로 생각해볼 문제가 있다.

 

1->2로 가는 그래프가 있다 가정해보자. 1번 노드에서 시작해 후위표기 즉 post number를 각 노드에 붙인다 하면, 

1번 노드가 2번이 되고 2번 노드는 1번이 될 것이다.

 

2에서 시작하는 후위표기를 하면 이 역시

1번 노드가 2번, 2번 노드가 1번을 갖게 될 것이다.

 

 이를 조금 생각해보면, 그래프에서 각 노드들을 후위 표기해보면 부모노드가 항상 자식 노드들보다 큰 값을 가지고 있음을 확인할 수 있다. 

그리고 이 특징은 지금 SCC 추출을 할 때에도 사용할 수 있다.

 

이를 생각하며 아래 그래프에서 SCC를 추출해보자.

 

 

 

 

 

 위 그래프의 어느 점을 잡아 순회한다고 생각하고 그 점은 트리의 루트이고 아래로 쫙 퍼진다 가정하면, 그 트리의 어느 지점의 부모 노드들이 각각의 SCC들을 구분하는 노드일 것이라 가벼운 생각을 할 수 있다.

 

 그리고, 그 부모 노드를 찾기 위해서는 바로 위에서 특징이라고 칭한 그래프 후위 표기를 해보고, 높은 후위표기 값을 갖는 노드가 즉 부모 노드의 역할을 하겠구나~ 라고 이해할 수 있다.

 

후위 표기 진행!!!

 

 

살짝 특이한 방법을 쓸건데, 이는 곧 모든 edge들의 방향을 바꿔주는 것이다.

엥? 이라는 생각이 들 수 있지만, 이는 SCC를 구하기 위해 꽤나 합리적인 방법이다.

 

 왜냐면, 서로 연결되어 있는 노드라면, 방향을 바꾼다 한들 그 연결관계가 깨지는 것이 아니기에 SCC에는 전혀 영향이 없고, SCC가 아닌 놈들의 연관관계를 끊어버리는 역할을 해주기 때문이다.

 

아래에서 진행할 높은 후위 표기 번호부터 탐색한다는 전략을 땡겨와서 조금만 더 면밀히 설명하자면,

 

엣지들의 방향을 바꾸어 탐색을 할때,

a노드 -> b노드로 움직일 수 있으려면 기존의 그래프에는 b -> a 로 연결되어 있어야 했다.

 

이를 위의 '특징' 과 함께 다시 생각해보면, b -> a 의 그래프라면 후위 표기에 의해 b가 무조건 높은 값을 가지고 있다.

 

그렇다면, 기존의 b -> a 는 엣지 방향이 바뀌어 a -> b 가 되고,

'진행할 전략' 에 의해 높은 번호인 b부터 탐색이 이뤄지기에, 엣지가 바뀐 그래프에서는 b에서 a로 갈 수 없는 상황이 되고, 이는 곧 a와 b가 서로 다른 SCC를 구성한다고 이해할 수 있는 것이다.

 

 

위의 설명이 진짠지 엣지들을 반전시켜보자

 

 

 

 

위 모습의 그래프가 되었다면,

우리의 전략은 후위 표기의 값이 높은 노드부터 탐색을 진행하는 것이다.

 

따라서 아래의 그림과 같은 순서로 SCC를 추출 할 수 있게된다.

 

 

 엣지가 바뀐 그래프에서 후위 표기가 큰 순서대로 탐색을 진행하면 각 step마다 SCC를 체크해 줄 수 있게된다!