[그래프] Graph 4: DFS의 응용: 간선 분류-dfs 스패닝 트리, 절단점, 강결합 컴포넌트 분리

1. 간선의 분류: 유향

dfs스패닝트리

dfs를 수행하면 그래프의 간선을 한 번씩은 조사하게 된다.

 

간선의 종류는 두가지가 있다.

 

- 처음 발견된 정점으로 연결된 간선

- 무시되는 간선

 

이들에 대한 정보를 수집하면 그래프 구조에 대해 많은 것을 알 수 있다.

일단 연결된 간선들만을 모아보면 트리 형태를 띠게 된다.

(위 그림은 0번 정점을 루트로 하는 트리 형태)

 

이 트리의 이름을 그래프의 깊이 우선 탐색의 스패닝 트리 혹은 DFS 스패닝 트리 라고 부른다.

 

 

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

 

- 트리 간선(tree edge) : 스패닝 트리에 포함된 간선

 

- 순방향 간선(forward edge) : 스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선을 말한다.

                                            위 그림에서 빨간선

 

- 역방향 간선(back edge) : 스패닝 트리의 자손에서 선조로 연결된 간선 

                                       위 그림에서 파란선

 

- 교차 간선(cross edge) : 교차 간선은 트리에서 선조와 자손 관계가 아닌 정점들간에 연결된 간선들

                                   위 그림에서 초록선, 위 세가지 분류를 제외한 나머지.

 

 

 

위 분류는 항상 dfs 방문순서에 따라 달라질 수 있다.

 

 

 

2. 간선의 분류 : 무향

 

무향 그래프의 간선은 양방향으로 통행 가능하므로

 

교차 간선이 있을 수 없다

 

교차 간선이 생기려면 선조- 자손 관계가 아니어야 한다.

 

하지만 무향그래프에서는 방향과 상관없이 연결되어있으면 항상 이어지기 때문에 교차 간선이 있을 수 없다.

(u-v 가 교차 간선이기 위해서는 v가 먼저 방문된후 u를 방문하지 않고 종료해야하는데 u-v로 v가 종료되기전에 u에 방문함)

 

순방향 간선과 역방향 간선의 구분이 없다.

 

 

 

 

 

 

3. 간선 분류의 이용

간선의 분류는 그래프 알고리즘을 이해하고 증명하기 위한 도구로 유용하게 쓰인다

 

위상 정렬의 정당성 증명

위상 정렬 알고리즘은 dfs의 종료 역순으로 정점을 재배열하므로

 

dfs(u) 가 dfs(v)보다 일찍 종료될 경우 (재배열된 후 u가 뒤쪽에 있을때)

 

u에서 v로 가는 간선이 존재할 수 없다는 것만 증명하면 그 정당성을 보일 수 있다.

 

- (u, v)가 트리 간선이면 dfs(u)에서 dfs(v)를 호출했다는 말이다. 그러면 dfs(u)가 먼저 종료될 수 없다.

 

- (u, v)가 역방향 간선이라면 v가 u의 선조이므로 v에서 u로 가는 경로가 있다는 뜻. 여기에 (u,v) 가 있으면

   위상정렬은 DAG여야한다는 가정에 모순이 생김. (사이클)

 

- (u, v)가 순방향 간선이라면 u가 v의 선조이므로 dfs(u)가 먼저 종료하는 것은 불가능하다.

 

- (u, v)가 교차 간선이라면 v를 방문했다는 뜻이고, dfs(v)가 먼저 종료되었다는 뜻이다.

    (dfs(u)가 먼저 종료되었다는 가정에 모순) 

 

따라서 간선(u, v)는 존재할 수 없고, 위상 정렬의 정당성은 증명된다.

 

 

사이클 존재 여부 확인

사이클의 존재 여부는 역방향 간선의 존재 여부와 동치이다.

 

사이클이 있는 그래프를 깊이 우선 탐색할 경우

 

사이클에 포함된 정점 중 깊이 우선 탐색 과정에서 처음 만나는 정점을 u라고 하자

 

dfs(u)는 u에서 갈 수 있는 정점들을 모두 방문한 후에야 종료된다.

 

사이클에 포함된 u 이전에 있는 정점을 dfs(u)가 종료하기 전에 방문하게 되는데,

(v->u)

 

이 정점에서 u로 가는 정점은 항상 역방향 간선이된다. (선조이므로)

 

 

 

4. 간선을 구분하는 방법- 구현: 유향

 

가장 구분하기 쉬운 간선은 트리 간선이다. dfs를 따라 내려가는 간선이기 때문이다.

 

만약 dfs 실행중 정점v를 이미 방문했다고 하면 이것이 자손인지, 부모인지 알 수 없다.

 

따라서 탐색 과정에서  또 다른 정보들을 dfs중에 업데이트 시켜야 한다.

 

그 정보는 몇번째로 발견되었는지를 기록하는 것이다.

 

 

(u,v)를 검사하는데 v가 이미 방문된 상태라고 해보자,

 

이때 방문 순서를 이용해 (u, v)를 분류할 수 있는지 확인하면된다.

 

- (u, v) 가 순방향 간선이라면 v는 u의 자손이어야 한다. 따라서 v는 u보다 더 늦게 발견 되어야한다.

- (u, v) 가 역방향 간선이라면 v는 u의 선조여야 한다. 따라서 v는 u보다 일찍 발견 되었어야한다.

- (u, v) 가 교차 간선이라면 dfs(v)가 종류한 후 dfs(u)가 호출되어야 한다. 따라서 v는 u보다 일찍 발견되어야 한다.

 

 

이처럼 발견 순서 정보를 이용하면 해당 간선이 순방향 간선인지를 알아낼 수 있다.

 

역방향 간선과 교차 간선을 구분 짓기위해 선조인지 아닌지를 알아야하는데

 

이는 dfs(v)가 종료되었는지 확인함으로써 구분 지을 수 있다.

(종료하지 않았으면 선조라는 것이므로 역방향 간선, 아니면 교차 간선)

 

 

*무향에서는 discovered[]만 있으면 모든 간선을 구분할 수 있다 (교차 간선이 없음)

 

vector<vector<int> > adj;
vector<int> discovered, finished;
int counter;
 
void dfs2(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;
            dfs2(there);
        }
        else if(discovered[here] < discovered[there])
            cout<<"forward edge"<<endl;
        else if(finished[there] == 0)
            cout<<"back edge"<<endl;
        else
            cout<<"cross edge"<<endl;
    }
    finished[here] = 1;
}
 

 

절단점 찾기 알고리즘(cut vertex): 무향

색 있는 정점이 절단점이다.

 

무향 그래프의 절단점:

    이 점과 인접한 간선들을 모두 지웠을 때 해당 컴포넌트가 두개이상으로 나뉘어지는 정점

 

 

절단점은 해당 정점이 없어지면 전체 네트워크가 마비됨을 의미하므로 현실 세계에서 중요한 의미를 가진다.

 

 

어떤 정점이 절단점인지 확인하는 간단한 방법은

 

해당 정점을 삭제한 뒤, 컴포넌트의 개수가 이전보다 늘어났는지를 확인하는 것이다.

 

이는 dfs를 |V|번 수행하면 간단하게 찾을 수 있다.

 

하지만 탐색 과정에서 얻는 정보를 잘 이용하면 한 번의 dfs로 모든 절단점을 찾을 수 있다.

 

 

무향 그래프의 스패닝 트리에는 교차 간선이 없으므로 연결되는 정점은 모두 선조 아니면 자손이다.

(위 그림에서 교차 간선이 생길 수 없기 때문에 정점 0 의 서브 트리들은 7로 가는 선을 제외하면 서로 연결되어 있지 않는다, )

 

정점 0이 지워져도 쪼개지지 않는 유일한 경우는

 

위 그림처럼 서브트리에 정점0의 선조와 자손들이 서로 연결되어 있는 경우이다.

 

즉 한 정점의 자손들이 모두 역방향 간선을 통해 그 정점의 선조로 올라갈 수 있다면 절단점이 아니게 되는것이다.

 

 

이것을 확인하기 위해서는

 

각 정점을 루트로 하는 서브트리에서 역방향 간선을 통해 갈 수 있는 정점의 최소 깊이를 반환하도록 해야한다.

 

(루트인 경우, 자손이 하나도 없거나 하나밖에 없는 경우는 예외이다, 즉 루트에서의 절단점은 두개 이상의 자손이 있어야함)

 

 

정점의 깊이를 비교하는 대신 각 정점의 발견 순서로 비교하는 형태도 상관은 없다.

 

dfs에서 선조들은 항상 먼저 발견되기 때문이다.

 

따라서 서브트리의 가장 낮은 곳을 들리는 간선이 있으면 계속 최저값으로 업데이트해주고

 

만약 서브트리의 루트보다 서브트리 에서 올라가는 정점들이 더 늦게 발견되면 이는 절단점이 된다는 것을 의미한다.

 

 

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);
        }
        else
            ret = min(ret, discovered[there]);
    }
    if(isRoot) isCutVertex[here] = (children >= 2);
    return ret;
}

 

 

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

 

이는 임의의 한 정점을 그래프에서 지우더라도 정점간의 연결관계가 유지된다.

 

 

그래프에서 다리를 찾기 (bridge)

어떤 간선을 삭제했을 때 이 간선을 포함하던 컴포넌트가 두개의 컴포넌트로 쪼개질 경우 

 

이 간선을 다리라고 부른다.

 

그래프에서 다리를 찾는 문제는 절단점을 찾는 알고리즘을 간단히 변형해서 풀 수 있다.

 

 

다리는 항상 트리 간선일 수 밖에 없다.

 

어떤 간선 (u,v)가 순방향이나 역방향이라면 부모-자손관계가 있다는 뜻이므로

 

(u, v) 말고 다른 경로가 있다는 뜻이기 때문이다.

 

 

 

또 다른 경로가 있으면 안되므로 트리 간선 (u,v) 가 

 

서브트리와 이외의 점을 연결하는 유일한 간선이어야 한다.

 

따라서 역방향 간선 중 자신의 부모로 가는 간선을 무시하도록 한뒤

 

v와 그 자손들에서 역방향 간선으로 닿을 수 있는 정점의 최소 발견 순서가 u후라면

 

(u, v)가 다리라고 판정할 수 있다.

 

 

 

 

6. 강결합 컴포넌트 분리: 유향

 

사이클 있는 방향 그래프

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

 

방향 그래프에서는 두 정점이 간선을 통해 연결되어 있다고 해서 두 정점을 잇는 경로가  존재하는 것이 아니므로

 

절단점의 정의를 그대로 사용할 수 가 없다.

 

이중 결합 컴포넌트와 비슷하지만, 방향 그래프에서 정의되는 개념으로

 

강결합 컴포넌트(strongly connected components, SCC)가 있다.

 

 

 

방향 그래프 상에서 두 정점 u, v에 대해 양 방향으로 가는 경로가 모두 있을 때

 

두 정점은 같은 SCC에 속해 있다고 말한다.

 

SSC와 DAG

 

scc는 방향 그래프에서 각 scc사이를 연결하는 간선들을 모으면 scc들을 정점으로 하는 DAG를 만들 수 있다는 것이다.

 

이처럼 그래프의 정점들을 scc별로 분리하고

 

각 scc를 표현하는 정점들을 갖는 새로운 그래프를 만드는 과정을

 

그래프의 압축(condensation) 이라고한다.

 

 

 

scc는 사이클과도 밀접하게 연관되어 있다.

 

한 사이클에 포함된 정점들은 항상 같은 scc에 속해 있게 되기 때문이다.

 

반대로 한 scc에 속한 두 정점 사이를 잇는 양방향 경로를 합치면 두 정점을 포함하는 사이클이 된다.

(같은 정점을 두번 이상 지날 수도 있기 때문에 단순 경로가 아닐 수 있다.)

 

 

 

사이클과 같이 scc또한 현실 세게에서 중요한 의미를 갖는 개념이다.

 

한 그래프가 두 개 이상의 scc로 나눠진다면, 이는 한 지점에서 다른 지점으로 갈 수 없다는 것을 의미한다.

 

 

 

7. 강결합 컴포넌트 분리를 위한 타잔의 알고리즘(Tarjan)

정점 밑부분 부터 조사

주어진 그래프를 scc로 분할하는 간단한 방법은 모든 정점에서 한 번씩 dfs를 수행하는 것이다.

 

그러면 모든 정점 쌍에 대해 양방향 경로가 모두 있는지 쉽게 확인할 수 있다.

 

하지만 이러한 방법은 O(|V||E|) 시간이 걸리기 때문에 그래프가 커질 경우 사용할 수 없다.

 

 

 

강결합 컴포넌트 분리를 위한 타잔의 알고리즘은 한 번의 dfs으로 각 정점을 scc별로 분리한다.

 

우선 임의의 정점에서부터 dfs를 수행해 dfs스패닝 트리를 만든다.

 

위 그림처럼 적절히 스패닝트리를 자르기만 해도 정점들을 scc로 분리할 수 있다

 

 

dfs 스패닝 트리를 만들고 그 트리를 적절히 자르기만해도 scc를 분리할 수 있다는것의 증명은 다음과 같다.

 

- dfs가 어떤 scc를 처음 방문했고 이 정점이 x라고 하자.

 

- 한 scc에 속한 두정점 간에는 항상 경로가 있기 때문에,

 

- dfs가 종료하기전에 같은 scc에 속한 정점을 전부 방문하게 된다.

 

- 따라서 이 scc에 속하는 정점 모두 x를 루트로 하는 서브 트리에 포함된다.

 

 

-스패닝 트리를 잘라서 scc를 분리할 수 없는 유일한 경우는 x와 같은 scc에 속한 정점 y 사이에 다른 ssc정점 z가 끼어 있는 경우 뿐이다.

 

-그러나 이 경우 z에서 y로 가는 경로와 y에서 x로 가는 경로를 합치면 z에서 x로 가는 경로를 만들 수 있다.

 

-따라서 z또한 같은 scc에 속해야하고 원래 가정이 모순이 된다.

 

 

 

 

8. 타잔 알고리즘 수행 과정: 간선을 자르는 조건

 

타잔의 알고리즘은 dfs를 수행하면서 각 정점을 scc로 묶는다.

 

이를 위해 간선을 따라 재귀 호출이 반환될 때마다, 이 간선을 자를지 여부를 결정한다.

 

 

탐색을 수행하면서 각 서브트리에 대한 정보를 수집한 후에야 간선을 자를지 말지 결정할 수 있기 때문이다.

 

만약 간선을 자르기로 하면, 하나의 scc를 새로 만든다. 

 

 

 

-어떤 정점 v를 루트로 하는 서브트리를 탐색한 뒤, 그 부모인 u로 재귀호출을 반환하면서

 

-트리 간선(u, v) 를 자르기로 결정헸다고 하자.

 

-v를 루트로 하는 서브트리는 모두 탐색한 후이므로,

 

-이 서브트리의 어떤 간선을 잘라야 할지 이미 모두 파악한 상태이다.

 

-아직 잘리지 않은 간선으로 v와 연결된 정점들을 모두 모아서 하나의 scc로 묶어준다.

 

 

 

각 간선을 자를지 여부는 다음과 같다.

 

트리 간선(u, v)를 자른다는 것은 v에서 u로 갈 수 있는 경로가 없다는 뜻이다.

 

v에서 u로 가는 경로에는 항상 역방향 간선이 하나 이상 포함되어 있어야 하므로

 

절단점 판단 알고리즘과 같이 v를 루트로 하는 서브트리를 탐색하면서

 

만나는 역방향 간선을 이용해 닿을 수 있는 가장 높은 정점을 찾는다.

 

이 정점이 u 혹은 그보다 높이 있는 정점이라면 이 역방향 간선을 통해 v에서 u로 갈 수 있고, 따라서 간선(u, v)를 잘라선 안된다.

 

교차간선 5->3 에 의해 모든 정점이 같은 SCC

교차간선 5->3이 scc를 만들지 않음

절단점 알고리즘은 무향 그래프에 대해 동작했으므로 역방향만 신경쓰면되지만

 

방향그래프를 다루는 타잔 알고리즘은 교차 간선을 신경써야한다.

 

 

위 그림처럼 두가지 경우가 생기는데

 

이 두가지 경우는 교차 간선을 따라가 만난 정점이 이미 SCC로 묶여있는지 여부를 이용하여

 

이 교차 간선을 통해 조상으로 올라갈 수 있는지를 판단할 수 있다.

(0 번과 끊어지는 간선이 하나라도 있을경우 아래 그림처럼 별도의 scc로 묶여 있어야한다.)

 

 

 

 

끊을 수 없는 경우들을 정리하자면 다음과 같다.

 

1. v를 루트로 하는 서브트리에서, v보다 먼저 발견된 정점으로 가는

    역방향 간선이 있다면 (u, v)를 끊어서는 안된다.

 

2. 그런 역방향 간선이 없더라도, v보다 먼저 발견되었으면서

    아직 scc로 묶여 있지 않은 정점으로 가는 교차 간선이 있더라도 (u, v)를 끊어서는 안된다.

 

 

 

 

9. 타잔 알고리즘의 구현

 

scc가 실제 dfs를 구현한 부분

tarjanscc는 배열과 카운터를 초기화하고 scc를 호출한다.

 

 

vector<vector<int> > adj;
vector<int> sccId;
vector<int> discovered;
stack<int> st;
 
int sccCounter, vertexCounter;
 
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];
        if(discovered[there] == -1)
            ret = min(ret, scc(there));
        else if(sccId[there] == -1)
            ret = min(ret, discovered[there]);
    }
    if(ret == discovered[here]) 
    {
        while(true) 
        {
            int t = st.top();
            st.pop();
            sccId[t] = sccCounter;
            if(t == here) break;
        }
        ++sccCounter;
    }
    return ret;
}
 
vector<int> tarjanSCC()
{
    sccId = discovered = vector<int>(adj.size(), -1);
    sccCounter = vertexCounter = 0;
    for(int i = 0; i < adj.size(); i++) if(discovered[i] == -1) scc(i);
    return sccId;
}

 

SCC묶기

 

이 알고리즘에서 눈여겨볼 부분은 현재 위치를 루트로 하는 서브트리에 남아 있는 정점들을 모두 찾는 방법이다.

 

간선을 끊기로 결정하면

 

서브트리에 남아 있는 정점들을 모두 한 scc로 묶은 뒤 이들을 그래프에서 지워야한다.

 

이런 작업을 하는 대신 스택을 이용하여 더 구현을 쉽게 할 수 있다.

 

 

scc는 dfs과정에서 방문한 정점들의 번호를 담는 스택을 유지한다.

 

이 스택은 지금까지 방문한 정점 중 아직 scc로 묶이지 않은 모든 정점의 번호이다.

 

각 정점을 처음 방문할때마다 스택에 넣기 때문에 스택에서 here 위에 들어있는 정점들은 모두 here의 후손들이다.

 

따라서 스택을 이용하면 here의 후손이면서 아직 다른 scc로 묶이지 않은 정점들을 쉽게 얻을 수 있다.

 

 

역방향 간선, 순방향 간선, scc로 묶이지 않은 교차 간선 간의 구분이 없다.

 

ssc가 dfs와 다른 것은 스택에서 정점을 꺼내는 반복문뿐이다.

 

타잔 알고리즘 시간 복잡도

 이는 분할 상환 분석을 이용하면  이 반복문의 총 수행 회수가 O(|V|) 라는 것을 알 수 있고

 

 알고리즘 전체의 시간 복잡도는 O(|V| + |E|) 가 된다.

 

 

SCC의 위상 정렬

 새 SCC가 생겨나는 시점은 항상 ssc함수가 종료하기 직전이다.

 

 이와 같은 속성 때문에 각 SCC는 위상정렬의 역순으로 번호가 매겨진다.

 

 dfs가 늦게 종료하는 정점부터 배열하면 그래프의 위상 정렬 결과를 얻을 수 있는 것과 마찬가지다.

 

 이와 같은 속성을 이용해 직접 그래프의 압축을 구현할 필요 없이 간단히 문제를 풀수 있는 경우가 있다고한다.

 

 

- 알고리즘 문제해결전략 850p