5. DFS - 간선의 분류와 컴포넌트 분리

DFS와 간선의 분류

DFS를 실행할 때 각 정점에서 연결된 여러 간선들 중에 아직 방문하지 않은 정점과 연결된 간선을 따라가게 된다.

이 때 각 정점에서 따라가는 간선들만을 모아보면 트리형태가 된다.

이런 트리를 그래프의 dfs 스패닝 트리라고 한다.

dfs 스패닝 트리를 생성하고 나면 그래프의 모든 간선을 4가지로 분류할 수 있다.

위 그림에서 검정색 실선으로 그려진 것이 그래프의 dfs 스패닝 트리이다.

이 그래프에서 4가지의 간선을 모두 살펴볼 수 있다.

1. 트리 간선 : dfs 스패닝 트리에 포함된 간선을 의미한다.

2. 순방향 간선 : dfs 스패닝 트리의 선조 정점에서 자손 정점으로 연결되지만 트리 간선이 아닌 간선을 의미한다.

3. 역방향 간선 : dfs 스패닝 트리의 자손 정점에서 선조 정점으로 연결되는 트리 간선이 아닌 간선을 의미한다.

4. 교차 간선 : 위 세가지 분류를 제외한 나머지 간선으로, 트리에서 선조와 자손관계가 아닌 정점들 간에 연결된 간선을 의미한다.

위의 간선 분류는 방향 그래프일 때의 경우이다.

그렇다면 무향 그래프일 때는 간선을 어떻게 분류할까?

우선 무향 그래프는 간선의 방향이 없으므로, 순방향 간선과 역방향 간선의 구분이 없다.

또한, 그래프의 모든 간선은 양방향 통행이 가능하므로 교차 간선이 없다.

간선을 구분하는 방법

그렇다면 그래프의 간선을 어떻게 구분할 수 있을까?

우선 트리간선은 가장 구분하기가 쉽다.

dfs(u)를 수행하는 도중 간선 (u,v)를 검사할때 정점 v가 방문된 적이 없다면 해당 간선을 따라가게 되기 때문에 (u,v)는 트리 간선이 된다는 것을 쉽게 파악 할 수 있다.

반면에 정점 v를 이미 방문했다면 해당 정점이 u의 조상인지, 자손인지, 둘 다 아닌지 알 수가 없다.

따라서 이것을 구분하기 위해 각 정점을 방문할 때 이 정점을 몇번째로 발견하였는지 번호를 기록해 두도록 한다.

그러면 u와 v의 발견 순서를 통해서 (u,v)의 간선 분류를 할 수 있다.

1. (u,v)가 순방향 간선이라면, u는 v의 조상이다. 따라서 u의 발견 순서가 v의 발견 순서보다 먼저이게 된다.

2. (u,v)가 역방향 간선이라면, u는 v의 자손이다. 따라서 u의 발견 순서가 v의 발견 순서보다 뒤여야 한다.

3. (u,v)가 교차 간선이라면, dfs(v)가 종료한 후 dfs(u)가 호출되어야 한다. 따라서 v가 u보다 먼저 발견 되어야 한다.

이렇게 판단하게 되면 발견 순서만으로는 2의 경우와 3의 경우를 구분할 수 없게 된다.

이 두 경우를 구분하기 위해서는 dfs(...)가 종료하였는지를 기록해 두는 것이다.

즉, dfs(v)가 이미 종료했다면 (u,v)는 교차간선이 될 것이고, 종료하지 않았다면 v는 u의 선조이기 때문에 역방향 간선이 될 것이다.

위와 같은 방법을 통해 간선의 분류를 구현할 수 있다.

// 그래프의 간선을 분류하는 dfs 구현

vector< vector<int> > adj;  // 그래프의 인접리스트

vector<int> discovered, finished;  // 각 정점의 발견 순서와 dfs(...)의 종료 여부

int counter;  // 정점 발견 순서를 세기 위한 카운터

void dfs(int here){

discovered[here] = counter++;

for(int i = 0; i < adj[here].size(); i++){

int there = adj[here][i];

cout << "(" << here << ", " << there << ") is a ";

// 아직 해당 정점에 방문하지 않았으면 트리간선

if(discovered[there] == -1){

cout << "tree edge" << endl;

dfs(there);

} 

// 해당 정점 방문 순서가 현재 정점 방문 순서보다 나중이면 순방향 간선

else if ( discovered[here] < discovered[there]){

cout << " forward edge" << endl;

} 

// 해당 정점에 대한 dfs(...)가 종료되었으면 역방향 간선

else if ( finished[there] == 0){

cout << "back edge" << endl;

} 

// 그 외의 경우는 교차 간선

else

cout << "cross edge" << endl;

}

finished[here] = 1;

}

절단점 찾기 알고리즘

dfs의 응용 문제 중 하나로 그래프의 절단점(cut vertex)을 찾는 문제가 있다.

어떤 무향 그래프에서 절단점이란 이 점과 인접한 간선들을 모두 삭제하였을 때 해당 컴포넌트가 두개 이상의 컴포넌트로 나누어 지는 정점을 말한다.

그래프에서 어떤 정점이 절단점인지 확인하는 방법은 

해당 정점을 그래프에서 삭제한 뒤 컴포넌트의 개수가 이전보다 늘어났는지를 보는 것이다.

컴포넌트의 개수는 dfs를 통해 간단하게 셀 수 있지만 이 과정을 모든 정점에 대해 반복해야 한다.

그러나 구현을 잘 하면 한번의 dfs를 통해 모든 절단점을 찾아낼 수 있다.

임의의 정점에서 시작하여 dfs를 수행해 dfs 스패닝 트리를 만든다고 하자.

이 때 어떤 정점 u가 절단점인지 어떻게 확인할 수 있을까?

우선 무향그래프는 교차간선이 없기 때문에 u와 연결된 모든 정점들은 u의 선조 아니면 자손이 된다.

위의 그림과 같이 u의 자손들이 각각 서브트리를 이루면서 존재하고 u의 위에는 u의 선조가 존재한다.

이 때 u의 서브트리들은 서로 연결되어 있지 않다.

이들을 서로 연결하는 간선이 있다면 그것은 교차 간선이 될텐데, 무향 그래프에는 교차간선이 존재하지 않기 때문이다.

위의 그림에서 u가 지워졌을 때 그래프가 두 개이상의 컴포넌트로 나누어지지 않는 유일한 경우는

u의 선조와 자손들이 모두 역방향 간선으로 연결되어 있는 경우이다.

즉, u의 모든 서브트리에서 각 서브트리에 포함된 정점 중 하나라도 u의 선조와 역방향 간선으로 연결된 것이 있다면, u는 절단점이 아니게 된다.

그러면 이렇게 역방향 간선이 존재하는지는 어떻게 확인할 수 있을까?

dfs(...) 함수를 통해 각 정점을 루트로 하는 서브트리에서 역방향 간선을 통해 갈 수 있는 정점의 최소 발견 순서를 확인하는 것이다.

u의 조상들은 항상 u보다 먼저 발견되기 때문에 u의 발견 순서보다 발견 순서의 번호가 작을 것이다.

즉, 그림에서 보면 u의 자손인 v1, v2, v3를 루트로 하는 서브트리에서 역방향 간선을 통해 갈 수 있는 정점의 최소 발견 순서가

모두 u의 발견 순서보다 숫자가 작으면 u는 절단점이 아니게 된다.

따라서 u의 자손 중 하나라도 u의 선조와 역방향 간선으로 연결되어있지 않은 게 있다면 u는 절단점이 될 것이다.

// 무향그래프에서 절단점을 찾는 알고리즘

vector< vector<int> > adj;  // 그래프의 인접리스트

vector<int> discovered;  // 각 정점의 발견 순서

vector<bool> isCutVertex;  // 각 정점이 절단점인지 여부

int counter = 0;  // 정점 발견 순서를 세기 위한 카운터

int findCutVertex(int here, bool isRoot){

discovered[here] = counter++;

// 해당 서브 트리가 연결되어있는 정점의 최소 발견 순서의 최대값은 루트의 발견순서 값

int ret = discovered[here];

// 해당 정점이 루트인 경우를 대비해 절단점 판정을 위해 자손 서브트리의 개수를 센다.

int children = 0;

for(int i = 0; i < adj[here].size(); i++){

int there = adj[here][i];

if(discovered[there] == -1){  // 아직 방문하지 않았다면 자손 서브트리의 루트가 된다.

children++;

int subtree = findCutVertex(there, false);  // 자손 서브트리에서 도달할 수 있는 정점의 최소 발견 순서

// 만약 현재 정점이 루트가 아닌데 자손 서브트리에서 도달할 수 있는 최소 발견순서가 현재 정점 이상이라면,

// 현재 정점은 절단점이 된다.

if( !isRoot && subtree >= discovered[here]){

isCutVertex[here] = true;

}

ret = min(ret, subtree);

}

// 이미 방문했다면 there는 here의 선조 정점이 된다.

// 즉, here를 루트로 한 서브트리에서 도달할 수 있는 정점의 최소 발견 순서의 후보가 된다.

else{

ret = min(ret, discovered[there]);

}

}

// 만약 현재 정점이 루트라면 자손 서브트리가 2개 이상일 때 현재 정점이 절단점이 된다.

if(isRoot){

if(children >=2) isCutVertex[here] = true;

}

return ret;

}

무향 그래프에서 절단점을 포함하지 않은 그래프를 이중 결합 컴포넌트(biconnected component) 라고 한다.

즉, 이중 결합 컴포넌트 내에서는 임의의 한 정점을 삭제해도 정점 간의 연결 관계가 유지된다.

절단점 사용 예제 - 다리(Bridge) 찾기

절단점 찾는 문제와 비슷하지만 약간 다른 것으로 그래프에서 다리를 찾는 문제가 있다.

그래프에서 어떤 간선을 삭제했을 때 이 간선을 포함하던 컴포넌트가 두 개의 컴포넌트로 쪼개질 경우 이 간선을 다리라고 부른다.

이 문제는 절단점을 찾는 알고리즘을 약간 변형해서 풀 수 있다.

우선 다리는 bfs 스패닝 트리의 트리 간선일 수밖에 없다.

어떤 간선 (u,v)가 순방향 간선이나 역방향 간선이면 u와 v를 잇는 또 다른 경로가 있다는 뜻이므로 (u,v)는 다리가 될 수 없기 때문이다.

따라서 트리 간선들에 대해서만 각 간선이 다리인지를 판단하면 된다.

dfs 스패닝 트리에서 (u,v)가 다리이기 위해서는 u가 v의 부모일 때, 

v를 루트로 하는 서브트리와 이 외의 점들을 연결하는 유일한 간선이 (u,v)여야 한다.

즉, (u,v)를 제외한 역방향 간선으로 u보다 높은 정점에 갈 수 없을 경우 (u,v)가 다리라고 판정할 수 있다.

절단점 사용 예제 - 강결합 컴포넌트 분리

이중 결합 컴포넌트의 개념은 무향 그래프에서만 정의된다.

절단점의 정의를 방향그래프에서 그대로 사용하기 어렵기 때문이다.

이중 결합 컴포넌트와 비슷하게 방향그래프에서 정의되는 개념으로 강결합 컴포넌트(strongly connected components, SCC)가 있다.

방향 그래프 상에서 두 정점 u와 v에 대해 양방향으로 가는 경로가 모두 있을 때 두 정점은 같은 SCC에 속해있다고 말한다.

위 그림에서 노란색 동그라미로 묶인 것들은 하나의 SCC이다.

그림을 보면 각 SCC들을 연결하는 간선들을 모으면 SCC들을 정점으로 하는 DAG를 만들 수 있다.

원 그래프의 정점들을 SCC별로 분리하고 각 SCC를 표현하는 정점들을 갖는 새로운 그래프를 만드는 과정을 그래프의 압축 이라고 한다.

SCC는 그림에서 확인할 수 있듯이 사이클과 밀접한 관련이 있다.

한 사이클에 포함된 정점들은 하나의 SCC안에 같이 속하게 된다.

강결합 컴포넌트 분리를 위한 타잔의 알고리즘

타잔의 알고리즘은 단 한번의 dfs로 각 정점을 SCC별로 분리한다.

우선 임의의 정점을 시작점으로 잡고 dfs를 수행하여 dfs 스패닝 트리를 만든다.

위 그림에서 가장 왼쪽 정점을 시작점으로 하여 dfs 스패닝 트리를 만들면 다음과 같다.

이 그림을 주목하여 보면, dfs 스패닝 트리를 잘 자르기만 해도 SCC로 분리할 수 있다는 점을 알 수 있다.

그래프에서 dfs를 진행하다가 임의의 정점 x에 대해서 해당 정점이 속한 SCC를 처음 방문했다고 해보자.

그러면 같은 SCC에 속한 정점들은 무조건 경로가 존재하기 때문에 dfs(x)는 종료하기 전에 같은 SCC에 속한 정점들을 모두 방문하게 될 것이다.

즉, 그림에서 빨간색으로 표시된 각 SCC의 루트가 되는 정점을 찾기만 하면 SCC를 분리하는 것은 어렵지 않다.

그러면 각 정점이 각 SCC의 루트인지 어떻게 판단 할 수 있을까?

스패닝 트리에서 인접한 두 정점이 서로 다른 SCC에 속한다면, 두 정점 중 자손 정점은 자신이 속한 SCC의 루트가 될 것이다.

어떤 정점 u가 SCC의 루트인지 판단하고자 할 때, u에서 선조로 가는 경로가 없어야 SCC의 루트가 된다.

u에서 선조로 가는 경로에는 반드시 역방향 간선이 포함되어야 한다.

그러므로 u를 루트로 하는 서브트리를 dfs 수행하면서 만나는 모든 역방향 간선을 이용해 도달할 수 있는 가장 상위 정점을 찾는다.

이 도달 가능한 최상위 정점이 u의 선조이거나 그보다 높이 있다면 이 역방향 간선을 통해 u에서 선조로 갈 수 있게 되고, 그러면 u는 SCC의 루트가 아니게 된다.

이 때 방향그래프에서는 교차 간선이 존재할 수 있기 때문에 역방향 간선을 찾아볼 때 교차간선이 아닌지 확인을 거쳐야 한다.

// 강결합 컴포넌트 분리를 위한 타잔의 알고리즘

vector< vector<int> > adj;  // 그래프의 인접리스트

vector<int> discovered, finished;  // 각 정점의 발견 순서, 각 정점에 대한 dfs(...) 함수 종료 여부 -> 간선 구분을 위함

vector<int> sccId;  // 각 정점의 컴포넌트 번호. 같은 강결합 컴포넌트에 속한 정점들의 컴포넌트 번호는 같다.

stack<int> st;  // 서브트리에 속하는 정점들의 번호를 담는 스택

int sccCounter, vertexCounter;  // 컴포넌트 번호와 발견 순서를 세기 위한 카운터

vector<bool> scced;  // 각 정점에 대해 컴포넌트 번호가 매겨졌는지 여부(이미 dfs가 종료되었는지 판단)

int scc(int here){

int ret = discovered[here] = vertexCounter++;

// 스택에 현재 정점을 넣는다. 이후 현재 정점의 후손들이 모두 스택에 들어간다.

st.push(here);

for(int i = 0; i < adj[here].size(); i++){

int there = adj[here][i];

// (here, there)이 트리 간선이라면(아직 해당 정점을 방문하지 않았다면)

if(discovered[there] == -1){

// 해당 정점을 루트로 하는 서브트리에서 도달할 수 있는 최소 발견 순서를 구한다.

ret = min(ret, scc(there));

}

// (here, there)이 역방향 간선이라면

else if(discovered[here] > discovered[there] && finished[there] == -1){   

// else if(!scced[there]) 과 같다(아직 scc(there) 함수가 종료되지 않았다면)

// there의 발견순서를 구한다.

ret = min(ret, discovered[there]);

}

}

// 현재 정점이 SCC의 루트인지 확인한다.

if(ret == discovered[here]){  // here을 루트로 하는 서브트리가 도달할 수 있는 가장 높은 위치가 here라면 SCC의 루트가 된다.

// 스택에 담아두었던 here의 서브트리에 속하는 정점들을 꺼내서 같은 SCC번호를 매겨준다.

while(1){

int t = st.top();

st.pop();

sccId[t] = sccCounter;

scced[t] = true;

if(t == here) break;

}

sccCounter++;

}

finished[here] = 1;

return ret;

}

vector<int> tarjanSCC(){

// 배열과 카운터 초기화

sccId = discovered = finished = vector<int>(adj.size(), -1);

scced = vector<bool>(adj.size(), false);

sccCounter = vertexCounter = 0;

// 모든 정점에 대해서 scc(...) 호출

for(int i = 0; i < adj.size(); i++){

if(discovered[i] == -1) scc(i);

}

return sccId;

}