January 16, 2021 19 min to read

그래프 자료구조 ②:깊이 우선 탐색②

그래프의 특성 중 하나인 SCC와 절단점에 대해서 알아봅시다

DFS 스패닝 트리와 간선의 분류

DFS 스패닝 트리를 설명하기 위해서, 우선 스패닝 트리가 뭔지 소개부터 해야겠지요.

그래프의 스패닝 트리란, 그래프의 정점을 모두 포함하는 트리를 의미합니다. DFS 스패닝 트리는, DFS 알고리즘을 통해서 만들어진 스패닝 트리를 의미합니다.

글로만 설명하는것보다는, 그림과 같이 설명하는 것이 좀더 이해하기 좋기에, 예시를 들어보겠습니다.

위의 그래프에서 DFS로 탐색을 했을 때, 사용한 간선을 노란색으로 표시한 그림은 아래와 같습니다.

위와 같이 DFS로 그래프를 탐색 하여, DFS 스패닝 트리를 만들고 나면, 그래프의 모든 간선을 4가지로 분류할 수 있습니다.

1. 트리 간선 (Tree edge)
   • 스패닝 트리에 포함된 간선. 그림 2에서는 노란색으로 표시된 간선입니다.
2. 순방향 간선 (Forward edge)
   • 스패닝 트리의 선조에서 자손으로 연결되지만, 트리 간선이 아닌 간선
   • 그림 2 에서는 (0,6)이 순방향 간선에 해당합니다.
3. 역방향 간선 (Back edge)
   • 스패닝 트리의 자손에서 선조로 연결되는 간선
   • 그림 2 에서는 (2,0)이 역방향 간선에 해당합니다.
4. 교차 간선 (Cross edge)
   • 트리간선, 순방향 간선, 역방향 간선이 아닌 간선
   • 스패닝 트리에서 부모와 자식 관계가 아닌 정점들끼리 연결된 간선
   • 그림 2에서는 (6,3)이 교차간선에 해당합니다
   • 무향 그래프(undirected graph)에서는 교차 간선이 존재하지 않습니다.

(u,v)가 교차간선이기 위해서는, v를 먼저 방문하고, u로 가지않고 검색이 종료되어야 하는데, 무향그래프에서는 (u,v)라는 간선이 있다면, u,v 상호간에 통행이 가능하므로, 그러한 일이 생길 수 없게 됩니다.

위에서 설명한 DFS 스패닝 트리의 간선 분류는 그 자체의 의미 보다는, 그래프와 그래프 관련 알고리즘을 이해하고, 설명하고, 증명하는데에 더 많이 쓰입니다. 아래의 항목들은 DFS 스패닝 트리와 간선의 분류를 통해서 설명되는 그래프 관련 알고리즘들 입니다.

위상정렬의 정당성 증명

우리가 전 포스팅에서 다뤘던 위상정렬 알고리즘은, dfs()의 종료 순서 역순대로 간선들을 배열하므로, dfs(u)가 dfs(v)보다 일찍 종료할 경우, \(u\)에서 \(v\)로 가는 간선이 존재할 수 없다는 것만 증명하면 그 정당성을 보일 수 있습니다. 이와 같은 간선이 존재할 수 있는지 알아봅시다.

1. \((u,v)\)가 트리 간선이라면 dfs(u)가 dfs(v)를 호출했다는 뜻인데, 그 경우에는 dfs(u)가 먼저 종료될 수 없습니다.
2. \((u,v)\)가 순방향 간선이라면, \(u\)가 \(v\)의 선조라는뜻인데, 이때 dfs(u)가 먼저 종료하는것은 불가능 합니다.
3. \((u,v)\)가 교차 간선이라면, dfs(v)가 종료하고 나서 \(u\)를 방문했다는 뜻인데, 이는 dfs(u)가 먼저 종료되었다는 사실과 모순입니다.
4. 역방향 간선에 대해서는, 역방향 간선이 있다는 것은 사이클이 있다는 것이므로 생각할 필요가 없습니다.

따라서 이와 같은 간선 \((u,v)\)는 존재할 수 없고, 위상 정렬의 정당성을 증명할 수 있습니다.

사이클의 존재여부 확인하기

그래프에서 사이클의 존재를 확인하기 위해서, 일반적인 DFS코드를 고쳐서 호가인해 보는것은 생각처럼 쉬운 일은 아닙니다. 하지만, 사이클의 존재 여부는 역방향 간선의 존재 여부와 동치이기 때문에, 이를 이용하면 간단히 이 문제를 풀 수 있습니다.

사이클이 있는 그래프를 깊이 우선 탐색할 경우 무슨 일이 벌어질지를 생각해 봅시다. 사이클에 포함된 정점 중 DFS과정에서 사이클에 포함된 정점 중 처음 만난 정점을 \(u\)라고 합시다. dfs(u)는 \(u\)이전에 갈 수 있는 정점들을 방문한 후에야 종료할 것이고, 따라서 DFS는 사이클에서 \(u\)이전에 있는 정점을 dfs(u)가 종료하기 전에 방문하게 되는데, 그러면 이 정점에서 \(u\)로 가는 정점은 항상 역방향 간선이 됨을 알 수 있습니다.

간선을 구분하는 방법

이제 간선의 구분이 어떤 영역에 쓰이는지를 알았으니, 어떻게 실제 그래프의 간선을 구분할 수 있는지 알아봅시다.

가장 구분하기 쉬운 간선은 트리간선 입니다. dfs(u)내에서 간선 \((u,v)\)를 검사했을 때, \(v\)가 방문된 적이 없다면 이 간선을 따라가므로 \((u,v)\)는 트리 간선이 되겠지요. 하지만, \(v\)가 이미 방문된 상황이라면 어떨까요? 이것만으로는 \(v\)가 \(u\)의 부모인지, 자손인지, 둘 다 아닌지 알 방법이 없습니다. 따라서, 탐색을 할 때, 방문 여부 외의 다른 정보를 저장할 필요가 있습니다. 방문 사실만이 아니라, 몇번째로 방문했는지 순서를 discovered[]에 저장한다고 합시다. 이 정보를 이용해서 순방향, 역방향, 교차 간선을 구분할 수 있는지 한번 알아봅시다.

• \((u,v)\)가 순방향 간선이라면, \(v\)는 \(u\)의 자손이여야 할 것입니다. 따라서 \(v\)는 \(u\)보다 더 늦게 발견되어야 합니다.
• \((u,v)\)가 역방향 간선이라면, \(v\)는 \(u\)의 선조여야 할 것입니다. 따라서 \(v\)는 \(u\)보다 일찍 발견되어야 합니다.
• \((u,v)\)가 교차 간선이라면, dfs(v)가 종료한 후, dfs(u)가 호출되어야 하므로, \(v\)는 \(u\)보다 일찍 발견되어야 합니다.

이렇게 정점 발견의 순서를 통해서, 간선의 분류에 도움을 받을 수 있습니다. 이때 역방향 간선과 교차 간선을 둘다 발견 순서 만으로는 구별이 불가능 하기 때문에, dfs(v)가 종료했는지를 확인하는 방법을 함께 사용하면 됩니다.dfs(v)가 아직 종료하지 않았다면, \(v\)는 \(u\)의 선조이니, 역방향 간선일 것이고, 아니라면 위에서 언급한대로, 교차간선임을 알 수 있을 것입니다.

위의 아이디어를 코드로 옮긴것이 아래의 코드 2 입니다. 아래의 코드에서 discovered[]가 기존 DFS의 visited[]를 대체한것을 눈여겨 보세요.

vector<vector<int> > adj;//그래프의 인접리스트 표현
//discovered : 간선의 발견 순서 finished[i] : dfs(i)가 종료되었음 1 아니면 0
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;
        }
        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;
}

코드 2 : 그래프의 간선의 분류를 시행하는 코드

이제 실제로 어떻게 간선을 분류하는지 알았으니, 간단한 응용으로 그래프의 사이클 판별을 해봅시다.

vector<vector<int>> adj;
vector<bool> vis, finished;
bool hasCycle;

void DFS(int node)
{
    vis[node] = true;
    for (int i = 0; i < adj[node].size(); ++i) {
        int next = adj[node][i];
        if (!vis[next])
            DFS(next);
        else if (finished[next] == false) { //  next가 이미 방문했지만, 종료되지 않는 정점이면
            hasCycle = true;
        }
    }
    finished[node] = true;
}

코드 3 : 그래프에서 사이클이 있는지 판별하는 코드 (출처 : https://hy38.github.io/finding-cycles-in-graph)

절단점 찾기 알고리즘

DFS를 응용해서 풀 수 있는 좀 더 본격적인 문제를 다루어 볼까 합니다. 무향 그래프에서 절단점(cut vertex)이라고 불리는 정점이 있습니다. 절단점이란, 그 정점과, 인접한 간선들을 모두 지웠을 때, 해당 컴포넌트가 두개 이상으로 나눠지는 정점을 말합니다. 예를 들어서 아래의 그림 3번에서는 1,3,5번 간선이 절단점이 됩니다. 그림 3 : 한 그래프에서 절단점의 예시

절단점을 찾는 문제는 현실세계에서도 중요하게 다뤄집니다. 위의 그래프의 정점이 네트워크 중계소이고, 간선이 중계소를 연결하는 통신선이라고 한다면, 절단점에 해당하는 정점이 고장나면, 다른 지역에 생기는 파급력이 더 크기 때문이죠.

어떤 정점이 절단점인지 간단히 확인하는 방법은 해당 정점과 인접하는 간선을 그래프에서 떼보고 컴포넌트의 개수가 더 늘었는지 확인하는 방법입니다. 그렇다면, 컴포넌트의 개수는 어떻게 셀 수 있을까요? DFS와 같은 그래프 탐색 알고리즘을 이용해서 그래프의 컴포넌트의 수를 셀 수 있습니다. 일반적인 DFS로 모든 정점의 절단점 여부를 확인하려면 DFS를 \(\|V\|\)번 수행해야 하지만, 탐색 과정에서 얻는 정보를 잘 활용하면 한번의 DFS만으로 모든 절단점을 찾을 수 있습니다.

임의의 정점에서 DFS를 수행해서, DFS 스패닝 트리를 만듭니다. 무향 그래프의 스패닝 트리에는 교차 간선이 없으므로, 어떤 정점 \(u\)와 연결된 정점은 부모 아니면 자식입니다. 이때 \(u\)의 자식들이 부모 노릇을 하고있는 서브트리들은 서로 연결되어있지 않습니다. 이유는 간단합니다. \(u\)의 자식들이 부모인 서브트리들이 서로 연결되어 있다면, 그 연결된 간선은 교차간선일 것인데, 무향 그래프에서는 교차간선이 존재하지 않으므로, 이는 모순임을 쉽게 알 수 있습니다. 따라서, \(u\)와, 그 인접한 간선이 없어졌을 때, 전에 언급했던 그 서브트리들과, \(u\)의 부모(있다면)가 서로 다른 컴포넌트로 쪼개지지 않으려면, 이들이 역방향 간선으로 연결되어있는 방법밖에 없습니다. 이 점에 착안해서, 각 정점을 루트로 하는 서브트리에서 역방향 간선을 통해서 갈 수 있는 정점들 중에서 최소 깊이를 반환하게 하는 것입니다. 만약에 \(u\)의 자손들이 \(u\)의 선조에게 역방향 간선을 통해서 갈 수 있다면 \(u\)는 절단점이 아니게 되지요.

여기서 의문이 하나 들 수 있습니다. 만약에 \(u\)가 루트라서, \(u\)의 선조라는게 존재하지 않는다면 어떻게 될까요? 당연히 \(u\)가 절단점일것이다 라고 생각할 수 있지만, 빠뜨리기 쉬운 예외가 있습니다. 자손이 하나도 없거나, 자손이 하나밖에 없다면, \(u\)를 제거해도, 컴포넌트의 개수가 증가하지 않기 때문이죠.

실제로 이 아이디어를 코드로 옮길때는, 각 정점의 깊이를 비교하는 대신, 각 정점의 발견 순서를 비교하는 방법으로 구현을 좀 더 간단히 할 수 있습니다. 우리가 알고 싶은것은 사실 깊이가 정확히 어떻다가 아니라, 해당 서브트리가 \(u\)의 조상과 연결되어있나 인데, \(u\)의 조상들은 항상 \(u\)보다 일찍 발견되는것을 이용하면 되지요.

이상 다뤘던 점들을 총 집합하여 코드로 옮긴것이 다음의 코드 4 입니다.

vector<vector<int> > adj;//그래프의 인접 리스트 표현
vector<int> discovered; //발견순서. 초기화는 -1로
vector<bool> isCutVertex;
int counter = 0;

//here를 루트로 하는 서브트리에 있는 절단점을 찾는다
//반환값은 해당 서브트리에서 역방향 간선으로 갈 수 있는 정점 중 가장 일찍 발견된 정점의 발견 시점
int findCutVertex(int here, bool isRoot){
    discovered[here] = counter++;
    int ret = discovered[here];

    int children = 0;
    for(int i = 0 ; adj[here].size(); ++i){
        int there = adj[here][i];
        if(discovered[there] == -1){ //가보지 않은 정점이면
            ++children;
            //subtree : 서브트리에서 갈 수 있는 가장 높은 정점의 발견 시점
            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;
}

코드 4 : 그래프에서 절단점을 찾는 코드

무향 그래프에서 절단점을 포함하지 않는 서브그래프를 이중 결합 컴포넌트(biconnected component)라고 합니다. 이중 결합 컴포넌트 내에서는 해당 컴포넌트 내의 임의의 정점을 하나 지워도 정점간의 연결관계가 유지된다는 특징이 있습니다.

다리 찾기

절단점 찾기와 비슷하지만 조금 다른 문제도 있습니다. 어떤 무향 그래프에서 어떤 간선을 삭제했을 때, 이 간선을 삭제했을 때, 컴포넌트가 쪼개진다면, 그 간선을 다리(bridge)라고 합니다. 예를 들어서 위의 그림 3에서는 \((0,1)\), \((3,4)\), \((5,6)\), \((5,7)\)이 다리가 되겠습니다.

절단점 찾기와 문제의 형태가 비슷한 만큼, 절단점 찾기 알고리즘을 약간 변형해서 풀 수 있습니다. 이 문제에 대해서 생각해 봤을때, 가장 먼저 깨달아야 할 점은 다리 역할을 하는 간선은 트리간선일 수 밖에 없다는 것입니다. 어떤 간선 \((u,v)\)가 순방향 간선이나 역방향 간선이라면, \(u\), \(v\)를 연결하는 다른 경로가 있다는 것인데, 이는 다리의 조건에 부합하지 않지요. 따라서, 트리 간선에 대해서만 다리인지 아닌지에 대해서 여부를 조사하면 됩니다.

DFS 스패닝 트리 상에서 \(u\)가 \(v\)의 부모일 때, 트리간선 \((u,v)\)가 다리가 되기 위해서는, \(v\)를 루트로 하는 서브트리와 이 외의 점들을 연결하는 유일한 간선이 \((u,v)\)가 되어야 합니다. 따라서, \((u,v)\)를 제외한 역방향 간선으로 \(u\)보다 높은 정점에 갈 수 없을 경우 \((u,v)\)가 다리라고 판별할 수 있겠지요.

이걸 코드로 옮기는 것은 매우 간단합니다. 위 코드 4에서, 절단점을 판별하는 조건인

if(!isRoot && subtree >= discovered[here])
                isCutVertex[here] = true;

이 부분의 조건을 참조하면 됩니다. isBridge[a][b]가 \((a,b)\)가 다리 인지 아닌지 저장하는 배열이라고 하면,

if(subtree > discovered[here])
                isBridge[here][there] = true;

이런식으로 쉽게 코드를 작성할 수 있습니다. >= 에서 >로 바뀐 이유도 생각해 보면 알 수 있지만, 간단히 설명하자면, 절단점은 정점도 없어지지만, 다리는 정점은 없어지지 않는다라는 점에 주목해서 생각해 보시면 될 것 같습니다.

강결합 컴포넌트(SCC)

절단점은 위에서도 살펴 보았듯, 무향 그래프에서만 정의되는 특수한 정점이었습니다. 유향 그래프에도 비슷한것이 있는데, 강결합 컴포넌트(Strongly Connected Components)라는 것입니다. 방향 그래프 상에서, 두 정전 \(u\)와 \(v\)에 대해서, 양방향으로 가는 경로가 모두 있을 때, 두 정점은 같은 SCC에 속해 있다고 합니다. 아래의 그림 4에서는, 같은 SCC에 속한 정점들을 사각형으로 묶음으로 구분해서 보여주고 있습니다. 그림 4 : 방향 그래프에서의 SCC 구분

SCC의 흥미로운 점은, SCC사이를 연결하는 간선들을 모으면, SCC들을 정점으로 하는 DAG(방향 비순환 그래프 = 사이클이 없는 방향 그래프)가 만들어 진다는 것입니다. 당연한 말입니다. 방향성은, 원본 그래프도 방향성이 있어서이고, 사이클이 없는 이유는, SCC들을 연결하는 간선 사이에 사이클이 있으면, 그건 별개의 SCC가 아니고, 하나의 SCC가 되니까요.

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

SCC는 사이클과 밀접한 연관이 있습니다. 한 사이클에 속한 정점은 항상 같은 SCC에 속해있게 되고, 반대로 한 SCC에 속한 두 정점 사이를 잇는 양방향 경로를 합치면, 두 정점을 포함하는 사이클이 됩니다.

SCC라는 개념은 현실세계에서 유용하게 쓰입니다. 일방통행 도로로 이루어진 도시의 도로망을 나타내는 그래프가 두개 이상의 SCC로 이루어져있다면, 한 지점에서 다른 지점으로 갈 수 없는 경우가 있다는 뜻이겠죠.

SCC분리를 위한 타잔의 알고리즘

주어진 그래프를 여러개의 SCC로 분할하는 가장 쉬운 방법은, 절단점을 찾을때와 같이 모든 정점에서 DFS를 수행하는 것입니다. 하지만 이 방법은 \(O(\|V\|\times \|E\|)\) 라는 시간을 소모하기 때문에, 그래프가 커진다면 사용하기 어렵습니다. SCC분해를 위한 타잔(Tarjan)의 알고리즘은 한번의 DFS로 각 정점을 SCC 별로 분리합니다. 타잔의 알고리즘은 이때까지 본 알고리즘보다, 유도하는 과정이 까다롭지만, DFS의 응용의 좋은 예 이므로, 숙지를 해놓도록 합시다.

알고리즘의 전제와 그 정당성의 증명

우선 임의의 정점에서 DFS를 수행해 DFS 스패닝 트리를 하나 만들어 냅니다. 이 스패닝 트리를 적절히 자르면 SCC들을 분리해 낼 수 있다는 것이 타잔의 알고리즘의 요지 입니다만…. 과연 그럴까요? 직관적으로 이렇다 하고 떠오르지는 않습니다.

사실 간단하게 증명할 수 있습니다. DFS가 한 SCC를 처음 방문하는 상황을 가정하여 그 SCC에서 처음 본 정점을 \(x\)라고 합시다. 한 SCC에 속한 두 정점간에는 항상 경로가 있음을 SCC의 정의로부터 알 수 있기에, DFS는 dfs(x)가 종료하기 전에 SCC의 모든 정점을 방문하게 될 것입니다. 따라서 아까 언급한 SCC는 \(x\)를 루트로 하는 서브트리에 포함됨을 쉽게 알 수 있습니다. 이때 스패닝 트리를 잘라서 분리할 수 없는 유일한 경우는 \(x\)와 같은 SCC에 속한 \(y\) 사이에 해당 SCC에 속하지 않는 다른 정점 \(z\)가 끼어 있을 경우 뿐인데, \(x\)에서 \(z\)로 가는 경로와, \(z\)에서 \(y\)로 가는 경로를 합치면, \(x\), \(y\), \(z\)가 하나의 SCC에 속해있다는 것을 알 수 있고, 전제가 모순임을 쉽게 알 수 있습니다.

실제 알고리즘의 구성

타잔의 알고리즘은 DFS를 수행하면서, 각 정점들을 SCC로 묶는 알고리즘 입니다. DFS가 반환될 때, 자손을 루트로 하는 서브트리에서 얼마나 스패닝 트리에서 높이가 높은 정점까지 갈 수 있는지 파악을 했던 위의 절단점 찾기 알고리즘 처럼, 타잔의 알고리즘도 비슷하게 접근합니다. DFS를 수행하고, 한 자식을 루트로 하는 서브트리에서 현재 DFS로 탐색중인 정점보다 더 높게 가지 못한다면, 그 자식을 루트로 하는 서브트리를 하나의 SCC로 묶을 수 있겠죠.(이를 간선을 자른다 라고도 표현하는 경우가 있습니다. 그래프에서 간선을 자르고 보면 시각적으로 SCC로 나뉜것을 볼 수 있으니까요)

여기까지는 앞의 절단점 찾기 알고리즘을 올바르게 이해했다면 딱히 달라진건 없습니다. 하지만 위의 절단점 찾기 알고리즘은 무향 그래프에서의 상황을 다루었다면, SCC 찾기 알고리즘은 유향 그래프에서의 상황을 다루기 때문에 한가지 더 고려해야 할 사항이 있습니다. 바로 무향그래프에는 없지만 유향그래프에는 있는 교차 간선 입니다.

정점 \(u\)를 방문하고 있고, \(u\)의 자식 정점 \(v\)에 대해서 탐색을 곧 할 상황을 생각해 봅시다. \(v\)를 루트로 하는 서브트리에서 \(v\)보다 일찍 발견된 정점으로 가는 간선이 없더라도, \((u,v)\)간선을 자르지 못하는(즉, \(u\), \(v\) 가 다른 SCC에 속한다고 단언할 수 없는) 상황이 생길 수 있습니다. 아래의 그림 5 에서 그러한 상황을 볼 수 있습니다. 그림 5 : 교차간선이 있을때의 SCC 판별을 어떻게 할까

위 그림에서 A로 표시된 경우를 살펴 봅시다. 정점에 적힌 번호대로 DFS 탐색을 했다고 가정할 때, 처음 dfs(0)이 실행 되고, dfs(1)을 실행 완료한 상황이라고 생각해 봅시다. 이제 0번 정점에서 4번정점을 보고 있는데, 4번 정점을 루트로 하는 서브트리 에서는 0번 정점이나, 0번 정점보다 먼저 발견된 정점으로 가는 경로는 존재하지 않습니다만, \(\)(0,4)\(\) 간선을 자를 수 없습니다. 교차간선 \((5,3)\)을 타면, \(4 \rightarrow 5 \rightarrow 3 \rightarrow 1 \rightarrow 0\) 라는 경로가 존재함을 알 수 있기 때문에, 그림 5의 A 경우에는 그래프 전체가 하나의 SCC로 묶임을 알 수 있습니다.

교차간선이 있다고 꼭 이런 경우가 발생하는 것이 아님을 위 그림 5의 B 경우가 잘 보여주고 있습니다. 이 경우에는 교차간선 \((5,3)\)을 사용해도, 0번 정점이나, 그보다 더 이르게 발견된 정점으로 다다를수 없기 때문에, 위 그래프는 하나의 SCC로 묶이는 것이 아닌, \(\{0\}, \{1,2,3\}, \{4,5\}\) 라는 세개의 SCC로 분할됨을 알 수 있습니다.

위 두가지 경우를 구분하는 방법을 생각해 봅시다. A 경우 에서는 교차간선으로 갈 수 있는 정점인 \(3\)을 이용해 \(0\)이나, \(0\)보다 먼저 발견된 정점으로 가려면, \(3\)에서 \(0\)이나 \(0\)보다 먼저 발견된 정점으로 가는 경로가 끊어짐이 없어야 할 것입니다. 만약에 끊어지는 부분이 하나라도 있다면 \(3\)은 이미 끊어지는 부분의 전 간선이 끊어지면서 별도의 SCC로 분리 되었을 것입니다. 이를 이용하면, 즉 한 정점이 SCC로 묶여있는지를 파악한다면, 그 정점을 통해서 조상으로 올라갈 수 있는지 여부를 파악할 수 있음을 여기서 알 수 있습니다.

이제 정리를 해 봅시다. SCC들을 분리하는 과정에서 트리 간선 \((u,v)\)를 끊으면 안되는 상황은

1. \(v\)를 루트로 하는 서브트리에서 \(v\)보다 먼저 발견된 정점으로 가는 역방향 간선이 있을 때
2. 그런 역방향 간선이 없다고 해도, \(v\)보다 먼저 발견되었으면서, 아직 SCC로 안묶여있는 정점으로 가는 교차간선이 있을 때

입니다. 이제 이를 어떻게 C++ 코드로 옮길지 다음 섹션에서 다루어 봅시다.

실제 코드 구현

//그래프의 인접 행렬 구현
vector<vector<int> > adj;
//각 정점의 scc번호. 같은 scc에 속해 있으면 번호가 같다.
//아직 어떤 scc에 속해있는지 판별이 안되었으면 -1
vector<int> sccId;
//각 정점의 발견 순서
vector<int> discovered;
//정점의 번호들을 담는 스택
stack<int> s;
int sccCounter, vertexCounter;

//here를 루트로 하는 서브트리에서 역방향 간선이나 교차간선을 통해서 갈 수 있는
//정점의 최소 번호를 반환한다.
//단 이미 SCC로 묶인 정점으로 가는 교차간선은 무시
int scc(int here){
    int ret = discovered[here] = vertexCounter++;
    s.push(here); //스택에 here를 넣는다. here의 후손들은 here 후에 들어가게 된다.
    for(int i = 0; i < adj[here].size(); ++i){
        int there = adj[here][i];
        if(discovered[there] == -1) //(here,there)가 트리 간선이면
            ret = min(ret, scc(there));
        else if(sccId[there] == -1)//만약 (here,there)가 무시하면 안되는 교차간선이면
            ret = min(ret, discovered[there]);
        }

    if(ret == discovered[here]){
        //there 들을 통해서 더 조상으로 못간다면 here을 루트로 하는 서브트리들을
        //하나의 SCC로 묶는다. 이를 스택을 이용해서 진행
        while(true){
            int t = s.top();
            s.pop();
            sccId[t] = sccCounter;
            if(t == here) break;
        }
        ++sccCounter;
    }
    return ret;
}

코드 5 : 타잔의 SCC 분리 알고리즘을 구현하는 코드 위 코드는 앞에서 설명한 알고리즘의 구성을 충실히 옮긴 코드입니다. 이 코드에서 주목할만한 부분은, here을 루트로 하는 서브트리들을 스택을 통해서 관리함으로, SCC를 묶을 때, 따로 서브트리를 찾아나서는 동작을 할 필요 없게 한 것 입니다.

위 코드의 scc()가 일반적인 깊이 우선 탐색과 다른것은 스택에서 정점을 빼내는 반복문 뿐인데, 스택에 들어가는 정점의 개수는 \(\|V\|\)임을 알 수 있으므로(없는 정점을 만들어서 넣을순 없고, 한 정점당 많아야 한번만 들어가니), 총 시간복잡도는 \(O(\|V\|+\|E\|)\)라는 것을 알 수 있습니다.

타잔의 알고리즘과 위상정렬

위 코드에서 SCC가 새로 생성되는 시점은, DFS가 종료되기 직전입니다. 위상정렬이 DFS 종료의 역순임을 생각해 볼 때, 각 SCC의 번호는 위상정렬의 역순으로 매겨지게 됩니다.

이 성질을 이용하면 그래프의 압축을 직접 구현하지 않고도 문제해결에 도움이 되는 정보를 알 수 있으니 잘 숙지했으면 좋겠습니다.

2-SAT 문제 풀기

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220803009418

정리를 잘 해 놓은 글이 있어 링크 첨부합니다.

참고한 글

https://hy38.github.io/finding-cycles-in-graph : 그래프 사이클 판별 관련

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(구종만 저)