알고리즘 공부[6] 그래프 절단점과 SCC

안녕하세요. 

오늘은 그래프의 절단점과 SCC(Strongly Connected Component)에 대해 알아보겠습니다.

Contents

Cut vertex(절단점 찾기)

SCC(Strongly Connected Component)

Kosaraju algorithm

Tarjan algorithm

Cut Vertex(절단점)

---

그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다.

이 때 그래프는 항상 undirected graph입니다.

1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다.

느낌상에는 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다.

그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니다.

그러나 이 방식은 각 정점마다 알고리즘을 돌려야 하니 정점이 많아 질수록 매우 불리해 집니다.

2) 무향그래프의 DFS Spanning tree를 보면 교차간선이 없다는 사실을 알 수 있습니다.

이 사실을 잘 이용해 봅시다.

한 정점 u를 기준으로 생각해 보면 u를 지웠을 때 절단점이 되지 않는 경우는 언제일까요?

DFS Spanning tree에서 u의 자식 정점을 root로 하는 sub tree에서 u의 선조로 역방향 간선이 모두 존재하면 됩니다. 

그렇게 되면 u를 지워도 u의 자식들이 root로 있는 sub tree는 모두 그대로 연결이 되어 그래프가 하나로 유지되기 때문입니다.

즉 u의 자식들이 root인 sub tree로부터 u의 선조로 가는 역방향 간선이 하나라도 없다면 u가 절단점이라는 사실을 얻었습니다.

이렇게 되면 DFS한번에 모든 절단점을 찾을 수 있으니 매우 효율적인 방법이 됩니다.

절단점을 찾는 방법

DFS spanning tree에서 정점 u의 자식들이 root가 되는 sub tree로부터 u의 선조로 가는 역방향 간선이 하나라도 없다면,

u는 절단점이다.

자 그럼 어떻게 구현하면 될까요?

아래 코드를 봅시다. 재귀적이라 조금 헷갈릴수 있기 때문에 주석을 달아놓았습니다.

천천히 읽어보시면 이해가 되실거라 생각합니다.

#include<cstdio>
#include<vector>
#define min(a, b) (((a) < (b))? (a) : (b))
using namespace std;
 
int cnt;
vector< vector<int> > adj;
vector<int> order;
vector<bool> isCutVertex;
 
/*
here를 root로 하는 tree에서 발견된 역방향 간선으로 이어진 정점 중
가장 상위 정점 order를 반환한다.
(전체 DFS spanning tree에서 상대적으로 가장 높은 정점의 순서)
*/
int findCutVertex(int here, bool isRoot) {
    order[here] = cnt++;
    int child = 0, ret = order[here];
    for (auto& there : adj[here]) {
        if (order[there] == -1) { //tree edge
            /* root인 경우 DFS spanning tree의 자식의 갯수를 알아야 한다. 
            자식의 갯수가 1개인 경우는 절단점이 될 수 없기 때문이다. */
            child++;
 
            /* 자식 sub tree에서 역방향 간선으로 가는 
            가장 상위 정점 order를 반환받는다. */
            int v_order = findCutVertex(there, false);
 
            /* 받은 order가 현재 정점의 순서보다 뒤라면 절단점이다. */
            if (!isRoot && v_order >= order[here])
                isCutVertex[here] = true;
 
            /* 현재 tree에서 갈 수 있는 가능한 상위 정점의 order를 업데이트 */
            ret = min(ret, v_order);
        }else {
            /* 역방향 간선으로 가는 정점 중 가장 상위 order를 업데이트*/
            ret = min(ret, order[there]);
        }
        
    }
    if (isRoot && child >= 2) isCutVertex[here] = true;
    return ret;
}
 

관련 문제를 백준에서 건져왔습니다. 문제를 풀어보고 다음내용으로 넘어갑시다.

문제 : https://www.acmicpc.net/problem/11266

#include<cstdio>
#include<vector>
#define min(a, b) (((a) < (b))? (a) : (b))
using namespace std;
 
int cnt;
vector< vector<int> > adj;
vector<int> order;
vector<bool> isCutVertex;
 
int findCutVertex(int here, bool isRoot) {
    order[here] = cnt++;
    int child = 0, ret = order[here];
    for (auto& there : adj[here]) {
        if (order[there] == -1) {
            child++;
            int v_order = findCutVertex(there, false);
            if (!isRoot && v_order >= order[here])
                isCutVertex[here] = true;
            ret = min(ret, v_order);
        }
        else if (order[there] < order[here]) {
            ret = min(ret, order[there]);
        }
    }
 
    if (isRoot && child >= 2) isCutVertex[here] = true;
    return ret;
}
 
int main() {
    int V, E;
    scanf("%d %d", &V, &E);
    adj = vector< vector<int> >(V+1);
    order = vector<int>(V+1, -1);
    isCutVertex = vector<bool>(V + 1, false);
    while (E--) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= V; i++) {
        if (order[i] == -1) {
            cnt = 0;
            findCutVertex(i, true);
        }
    }
    cnt = 0;
    for (int i = 1; i <= V; i++) {
        if (isCutVertex[i])
            cnt++;
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= V; i++) {
        if (isCutVertex[i])
            printf("%d ", i);
    }
    printf("\n");
}

조금 더 생각해보면 이런 문제도 풀 수 있습니다. (꼭 풀어보세요!)

문제 : https://www.acmicpc.net/problem/11400

#include<cstdio>
#include<vector>
#include<algorithm>
#define min(a, b) (((a)<(b))? (a):(b))
using namespace std;
 
int cnt;
vector<vector<int> > adj;
vector<int> order;
vector<pair<int, int> > cut_edge;
bool comp(const pair<int, int>&a, const pair<int, int>&b) {
    if (a.first == b.first) return a.second < b.second;
    else return a.first < b.first;
}
int findCutEdge(int here, int prev) {
    order[here] = cnt++;
    int ret = order[here];
    for (auto& there : adj[here]) {
        if (order[there] == -1) {
            int v_order = findCutEdge(there, here);
            if (v_order > order[here]) {
                if(here > there) cut_edge.emplace_back(there, here);
                else cut_edge.emplace_back(here, there);
            }
            ret = min(ret, v_order);
        }
        else if (prev!=there && order[there] < order[here]) {
            ret = min(ret, order[there]);
        }
    }
    return ret;
}
 
int main() {
    int V, E;
    scanf("%d %d", &V, &E);
    adj = vector<vector<int> >(V + 1);
    order = vector<int>(V + 1, -1);
    while (E--) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    findCutEdge(1, 1);
    sort(cut_edge.begin(), cut_edge.end(), comp);
    printf("%d\n", (int)cut_edge.size());
    for (auto&p : cut_edge) {
        printf("%d %d\n", p.first, p.second);
    }
}

이 문제에서는 21번 라인에서 if문의 조건문과 27번 라인에서의 조건을 잘 보셔야 합니다.

하위 subtree에서 자신보다 같거나 높은 순위의 정점으로 가는 역방향 간선이 없다면 절단선이라 할 수 있겠죠!

SCC(Strongly Connected Component)

---

자 우리는 위에서 undirected graph인 경우에 절단점과 절단선을 한번 찾아보았습니다. 

무향 그래프에서 절단점이 존재하지 않는 그래프를 우리는 Biconnected component라고 부릅니다. 

절단점이 없다면 그래프 상의 어떤 점을 삭제하더라도 임의의 두 정점은 서로로 가는 경로가 존재하게 됩니다.

Biconnected Component

Undirected Graph에서 절단점이 존재하지 않는 그래프

그렇다면 방향그래프의 경우는 어떨까요? 

방향그래프에서는 SCC(Strongly Connected Component)라는 개념이 있습니다.

방향그래프의 두 정점간 서로 양방향으로 가는 경로가 있을 때 두 정점은 한 SCC안에 포함된다고 정의를 합니다.

Strongly Connected Component

만약 그래프의 임의의 한 정점에 대해 다른 모든 정점으로 가는 경로가 존재한다면

그 그래프를 SCC(Strongly Connected Component)라고 한다.

즉 한 SCC안의 두 정점은 서로로 가는 양방향 경로가 존재하게 됩니다.

따라서 어떤 그래프가 두 개 이상의 SCC로 이루어 진다면, 

그 그래프 상에 두 정점 u, v에 대하여 u에서 v정점으로 가는 경로가 존재하지 않는 경우가 있다는 의미를 가집니다.

(아래 그림에서 2->4로가는 경로는 있으나 4->2로 가는 경로는 존재하지 않습니다. 따라서 4와 2는 같은 SCC로 볼 수 없습니다.)

아래 그림에서는 1, 2, 3 과 4, 5가 각각 SCC를 이룹니다.

자 이제 주어진 방향그래프에서 SCC를 검출하는 방법에 대해 알아봅시다.

Kosaraju algorithm(코사라주 알고리즘)

---

먼저 알아 볼 알고리즘은 코사라주 알고리즘입니다.

코사라주 알고리즘의 핵심은 위상정렬에 있습니다. 위상정렬이 이 알고리즘에서 핵심 역할을 합니다.

또한 역방향 그래프와 원래 그래프는 SCC가 같다는 것 또한 중요하게 작용합니다.

먼저 아이디어는 다음과 같습니다.

코사라주 알고리즘(Kosaraju's Algorithm)

1. 그래프의 모든 정점에 대하여 DFS를 통해 위상정렬을 하여 Stack에 저장합니다.
(정점을 방문하면서 DFS의 종료되는 순으로 Stack에 push 합니다.)

2. 원래 그래프의 역방향 그래프를 만듭니다. (모든 간선의 방향을 반대로 한 그래프를 만듭니다.)

3. 그다음 Stack에서 하나씩 pop하여 역방향 그래프에서 DFS를 진행합니다.

4. 3에서 DFS 한 번 할때 검출되는 모든 정점을 구하면 이것이 바로 SCC가 됩니다.

사실 위에 말을 보고 이해하면 좋겠지만, 처음보는 사람의 입장에서 설명이 와닿지는 않을 것입니다.

더군다나 이것이 동작하는 이유에 대해서도 말이죠.

간단히 살펴보며 이해해 봅시다.

아래 그림에서 오른쪽 그림은 왼쪽그림의 역방향 그래프 입니다.

1. 우선 두 그래프의 SCC는 같음을 알 수 있습니다. 

(당연히 방향을 바꾼다고 해서 SCC의 정의로 인해 SCC가 변화되지는 않기 때문입니다.)

2. 이제 왜 우리가 위상정렬방식으로 정점들을 정리하는지 생각해 봅시다!

아래와 같이 두 SCC가 존재한다고 합시다. 

그리고 SCC1의 정점 u로부터 SCC2의 정점 v로 가는 간선이 존재했다고 합시다.

코사라주 알고리즘을 살펴보면 모든 방문하지 않은 점에 대해 dfs를 수행하여 종료시점에서 stack에 정점을 기록합니다.

두 SCC간의 관계에 따라 다음과 같은 case가 존재합니다.

  1) SCC1 내부의 점 s1으로 부터 dfs가 수행이 먼저 되는 경우

  2) SCC2 내부의 점 s2으로 부터 dfs가 수행이 먼저 되는 경우

1)의 경우는 stack에 SCC2의 모든 정점이 SCC1의 s1 정점보다 아래에 위치하게 됩니다. 

DFS Spanning tree를 생각해 보아도 u를 root로 하는 서브트리의 정점들(u를 제외)은 모두 SCC2에 속하며, 

s1은 u보다 나중에 dfs가 종료되기 때문입니다.

즉, stack에서 pop을 하기 시작하면 SCC1 내부의 정점이 SCC2 내부의 정점보다 먼저 나오게 된다는 점을 의미합니다.

(모든 SCC1의 정점이 SCC2의 정점보다 먼저 나온다는 얘기는 아닙니다.)

2)의 경우는 stack에 SCC2의 모든 정점이 쌓인 후 SCC1의 한 정점을 기준으로 다시 dfs를 수행합니다.

이 경우는 모든 SCC2의 정점이 SCC1의 정점보다 stack에서 아래에 존재하게 됩니다.

역시나 stack에서 pop을 하기 시작하면 SCC1 내부의 정점이 SCC2 내부의 정점보다 먼저 나오게 됩니다.

그렇다면 이것이 코사라주 알고리즘에서 어떻게 작용할까요?

위 그래프의 역방향을 생각해 봅시다.

코사라주 알고리즘은 dfs를 수행한 후 stack에 기록된 정점들을 pop하면서 역방향 그래프에서 dfs를 수행합니다.

위의 1), 2)경우 모두 stack에서 pop을 하면 SCC1 내부의 정점이 먼저 나오게 됩니다.

그렇다면 위 SCC1에서 SCC2로 가는 간선이 없으므로 SCC1내부의 정점을 모두 방문한 후 dfs가 종료되게 됩니다.

이렇게 SCC1을 검출 할 수 있습니다.

그 다음 stack에서 pop을 하면서 방문여부를 확인하면 SCC2 내부의 정점에 대해 dfs가 수행이 되고, 

정점 v에서는 u가 이미 방문된 정점이므로 이 역시 SCC2의 정점을 모두 방문한 후 dfs가 종료되게 됩니다.

따라서 SCC2가 검출이 됩니다.

작동방식에서 위상정렬이 필요한 이유는 위와 같이 역방향 그래프에서 SCC를 검출하기 위해서 dfs 우선순위를 정해주기 위함입니다.

작게보면 정점간의 위상정렬이라고 볼 수 있으나, 여기서 하고자 하는 것은 SCC를 하나의 덩어리로 볼 때 그 덩어리 간의 위상정렬입니다.

(덩어리간의 그래프는 DAG이며, 논리적으로 SCC간의 위상정렬을 얻을 수 있습니다.)

물론 이 알고리즘의 time complexity는 DFS 2번으로

가 되고 인접 행렬 표현의 경우는

가 됩니다.

구현은 아래와 같습니다.

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
 
vector< vector<int> > adj, inv_adj;
vector<bool> visited;
vector<int> scc;
vector< vector<int> > ans;
stack<int> stk;
 
void dfs(int here, bool isInverse){
    visited[here] = true;
    vector< vector<int> >&g = isInverse? adj : inv_adj;
    for(int there : g[here]){
        if(!visited[there])
            dfs(there, isInverse);
    }
    if(isInverse) scc.push_back(here);
    else stk.push(here);
}
 
void kosaraju(){
    int n = adj.size();
    visited = vector<bool>(n, false);
    for(int i = 1; i<n; i++){
        if(!visited[i])
            dfs(i, false);
    }
    visited = vector<bool>(n, false);
    while(stk.size()){
        int v = stk.top();
        scc.clear();
        stk.pop();
        if(!visited[v]){
            dfs(v, true);
            ans.push_back(scc);
        }
    }
}

Tarjan algorithm(타잔 알고리즘)

---

두번째로 알아볼 알고리즘은 타잔 알고리즘 입니다.

이 알고리즘은 DFS한번에 모든 SCC를 검출하는 알고리즘입니다.

물론 한번에 끝내는 만큼 이해하기는 어려울 수 있습니다.

우선 원리를 좀 알아보죠.

직관적으로 알 수 있는 한가지 정보는 DFS를 돌면서 만들어지는 DFS spanning tree에서 간선을 적당히 자르면 

SCC를 구분 할 수 있다는 것입니다. 그렇다면 DFS를 한번 돌면서 모든 SCC를 적당히 구분해 낼 수 있다는 생각이 떠오릅니다.

그렇다면 어떻게 간선을 자를 수 있을까요?

앞서 배운 것 처럼 Directed graph의 DFS Spanning tree에는 forward edge가 없습니다. 

(즉, tree edge, cross edge, back edge만을 가집니다.)

그럼 우선 간단하게 spanning tree에서 cross edge도 존재하지 않는 경우를 살펴봅시다.

위와 같은 그래프에서 4번 정점을 기준으로 dfs를 수행하면 cross edge가 존재 하지 않는 DFS Spanning tree가 만들어 집니다.

이렇게 트리를 만들면서 할 수 있는 일은 간단합니다. leaf부터 올라오면서 해당 sub-tree가 SCC인지 판단하여 간선을 잘라내면 됩니다.

방식은 우리가 절단선을 검출하는 방식과 유사합니다.

위의 그림을 예로 설명해 보겠습니다. (설명을 보면서 이해해보고, 코드를 보면서 직접 그림을 그리며 수행해 보시길 권장합니다.)

1) 우선 4번 정점에서 dfs를 수행하면서 방문한 정점에 대한 순서를 저장합니다.

1번 정점은 1, 2번 정점은 2, 3번 정점은 3, 5번 정점은 4, 6번 정점은 5, 4번 정점은 6을 가지게 되겠죠.

2) 그렇게 순서를 저장하면서 가다가 3번 정점까지 도달하게 됩니다. 

3번 정점에서는 3번 정점이 갈 수 있는 최소한의 정점 순서를 계산하여 return 해줍니다. 

즉, 3번에서는 1번 정점까지 돌아가는 back edge가 있으므로 1을 return해 줍니다. (절단점 혹은 절단선을 잘라내는 기술과 동일합니다.)

3) 그리고 2번으로 돌아와 역시 1을 return해 줍니다.

4) 1번으로 돌아오고나면 간선 4->1을 잘라야 한다는 사실을 알 수 있습니다.

왜냐하면, 1번 정점이 root인 sub-tree에서 갈 수 있는 최소 순서의 정점이 자기 자신이기 때문입니다.

  u->v로 가는 간선에 대하여 해당 간선을 절단하여 SCC를 구분하기 위해서는 

  v를 root로 한 sub-tree에서 도달 할 수 있는 최소 순서의 정점이 v여야 합니다. 

(v보다 앞선 정점에 도달할 수 있다면 SCC가 되지 않고, 그 이후 정점에 도달한다면 SCC가 이미 밑에서 검출이 되었어야 하기 때문입니다.)

그렇게 되면 4) 과정에서 1, 2, 3이 같은 SCC로 구분됩니다.

5) 마찬가지로 6번 정점에서 5를 return하고 5번 정점에서는 return값이 5이므로 간선을 잘라야 되는 경우가 됩니다.

따라서 5, 6 정점이 같은 SCC로 구분이 됩니다.

6) 나머지 4번 정점은 자동적으로 단일 정점이 SCC가 되겠습니다.

위에서 우리는 cross edge가 없는 경우를 살펴보았습니다.

그런데 cross edge가 있는 경우는 어떻게 SCC를 구분지을 수 있을까요?

u->v로 가는 간선이 교차간선이라 해봅시다.

만약 u에서 v를 방문할 때 v가 아직 SCC로 절단되지 않는 경우라면  v에서 r로 가는 경로가 존재 할 것입니다.

(왜냐하면 정점 a에서 SCC로 묶이지 않았으므로 v에서 a보다 위의 정점으로 가는 경로가 존재하여 결국 r로도 갈 수 있기 때문입니다.)

그렇다면 r에서 u로 돌아오는 경로가 존재하므로 두 정점 v와 u는 같은 SCC에 존재 할 수 있습니다.

하지만 정점 v가 이미 SCC가 구분되어진 정점이라면 v에서 r로 오는 경로가 없으므로 v에서 u로 가는 경로 또한 없다는 말이 됩니다.

따라서 이미 구분되어진 정점 v로의 간선은 우리가 고려할 필요가 없습니다.

정리하면 교차간선에 대해서 도달하는 정점이 SCC가 아직 구분되어지지 않은 경우에만 

3)에서 했던 과정처럼 최소 순서 정점으로 계산하여 값을 return하면 됩니다. 

코드는 다음과 같습니다.

코드를 보고 직접 그림을 그려 이해하시길 바랍니다.

#include<cstdio>
#include<vector>
using namespace std;
 
vector<vector<int> > adj;
vector<int> order, sccId;
stack<int> st;
int sCnt, vCnt;
 
int getSCC(int here){
    int ret = discovered[here] = vCnt++;
    //All of child vertex node of here will be put above 'here'
    st.push(here);
    for(int there : adj[here]){
        if(order[here]==-1){
            //tree edge
            ret = min(ret, scc(there));
        }else if(sccId[there]==-1){
            //back edge, or cross edge linking same SCC
            ret = min(ret, order[there]);
        }
    }
    if(ret == order[here]){
        while(true){
            int t = st.top();
            st.pop();
            sccId[t] = sCnt;
            if(t == here) break;
        }
        sCnt++;
    }
    return ret;
}

여기서 Stack을 이용하는 이유는 같은 SCC인 정점들을 모아놓고 한번에 SCC로 묶기 위함입니다.

과정이 모두 수행되면 sccId에는 각 정점에 대해 SCC가 구분되어 기록됩니다.

역시 이 알고리즘 또한 dfs 1번으로 time complexity는

가 되고 인접 행렬 표현의 경우는

가 됩니다.

---

이번 글에서는 절단점과 SCC에 관련된 내용에 대해 알아보았습니다.

질문이 있으시거나, 잘못된 내용을 발견하시면 댓글 남겨주시면 답변드리겠습니다.

감사합니다.