강하게 연결된 그래프(Strongly Connected Graph) — 강연결 성분 찾기 알고리즘 완벽 가이드

강하게 연결된 그래프란 무엇인가?

강하게 연결된 그래프(Strongly Connected Graph)란 방향 그래프(Directed Graph)에서 하나의 컴포넌트(성분) 안에 속한 모든 정점 쌍 사이에 서로 도달 가능한 경로가 존재하는 경우를 말합니다. 즉, 임의의 두 정점 u와 v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 있어야 합니다.

방향 그래프를 강연결 성분(Strongly Connected Component, SCC) 단위로 나누면, 각 성분 내부의 정점들은 서로 양방향으로 도달할 수 있습니다.

강하게 연결된 그래프(Strongly Connected Graph) — 강연결 성분 찾기 알고리즘 완벽 가이드

알고리즘 개요 (코사라주 알고리즘)

이 문제는 코사라주(Kosaraju) 알고리즘을 통해 해결할 수 있으며, 핵심 절차는 다음과 같습니다.

DFS 수행: 원본 그래프에서 깊이 우선 탐색(DFS)을 실행하여 각 정점의 종료 시간(finish time)을 스택에 기록합니다.
그래프 전치: 모든 간선의 방향을 뒤집은 전치 그래프(transposed graph)를 만듭니다.
위상 정렬 순서로 탐색: 스택에서 정점을 꺼내는 순서(종료 시간 내림차순, 즉 위상 정렬 역순)대로 전치 그래프에서 다시 DFS를 수행하면, 각 탐색마다 하나의 강연결 성분이 얻어집니다.

입력 및 출력 형식

Input:
그래프의 인접 행렬
0 0 1 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 0

Output:
Following are strongly connected components in given graph:
0 1 2
3
4

위 입력 그래프에서 정점 0, 1, 2는 서로 순환하며 연결되어 하나의 강연결 성분을 이루고, 정점 3과 4는 각각 독립적인 성분입니다.

알고리즘 상세 설명

1. traverse(graph, start, visited)

입력: 탐색할 그래프, 시작 정점, 방문 여부 배열
출력: DFS 방식으로 각 노드를 순회하며 출력

Begin
    mark start as visited
    for all vertices v connected with start, do
        if v is not visited, then
            traverse(graph, v, visited)
    done
End

2. topoSort(u, visited, stack)

입력: 시작 노드, 방문 여부 플래그, 스택
출력: 그래프를 정렬하면서 스택을 채움

Begin
    mark u as visited
    for all node v, connected with u, do
        if v is not visited, then
            topoSort(v, visited, stack)
    done
    push u into the stack
End

3. getStrongConComponents(graph)

입력: 주어진 그래프
출력: 모든 강연결 성분 목록

Begin
    initially all nodes are unvisited
    for all vertex i in the graph, do
        if i is not visited, then
            topoSort(i, vis, stack)
    done

    make all nodes unvisited again
    transGraph := transpose of given graph

    while stack is not empty, do
        pop node from stack and take into v
        if v is not visited, then
            traverse(transGraph, v, visited)
    done
End

C++ 전체 구현 예제

#include <iostream>
#include <stack>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 0, 1, 1, 0},
    {1, 0, 0, 0, 0},
    {0, 1, 0, 0, 0},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};

int transGraph[NODE][NODE];

void transpose() {     // 그래프를 전치하여 transGraph에 저장
    for(int i = 0; i<NODE; i++)
        for(int j = 0; j<NODE; j++)
            transGraph[i][j] = graph[j][i];
}

void traverse(int g[NODE][NODE], int u, bool visited[]) {
    visited[u] = true;     // u를 방문 처리
    cout << u << " ";

    for(int v = 0; v<NODE; v++) {
        if(g[u][v]) {
            if(!visited[v])
                traverse(g, v, visited);
        }
    }
}

void topoSort(int u, bool visited[], stack<int>&stk) {
    visited[u] = true;     // 방문 표시

    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {     // u에 인접한 모든 정점 v에 대해
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }

    stk.push(u);     // 시작 정점을 스택에 푸시
}

void getStrongConComponents() {
    stack<int> stk;
    bool vis[NODE];

    for(int i = 0; i<NODE; i++)
        vis[i] = false;     // 초기에 모든 노드는 미방문 상태

    for(int i = 0; i<NODE; i++)
        if(!vis[i])     // 아직 방문하지 않은 노드인 경우
            topoSort(i, vis, stk);

    for(int i = 0; i<NODE; i++)
        vis[i] = false;     // 순회를 위해 모든 노드를 다시 미방문 처리
    transpose();     // 방향이 반전된 그래프 생성

    while(!stk.empty()) {     // 스택에 요소가 있는 동안 위상 정렬 순서로 처리
        int v = stk.top(); stk.pop();
        if(!vis[v]) {
            traverse(transGraph, v, vis);
            cout << endl;
        }
    }
}

int main() {
    cout << "Following are strongly connected components in given graph: "<<endl;
    getStrongConComponents();
}

실행 결과

Following are strongly connected components in given graph:
0 1 2
3
4

정리

코사라주 알고리즘은 DFS를 두 번 수행하는 방식으로 강연결 성분을 찾으며, 시간 복잡도는 O(V + E)로 매우 효율적입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 같은 문제를 해결하는 또 다른 대표적인 방법으로는 타르얀(Tarjan) 알고리즘이 있으며, 이 역시 선형 시간에 동작하지만 그래프를 전치할 필요가 없다는 차이점이 있습니다.

강연결 성분 분석은 소셜 네트워크 분석, 웹 페이지 랭킹, 컴파일러의 의존성 분석 등 다양한 실무 분야에서 활용되는 중요한 그래프 이론 기법입니다.