Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 그래프의 강연결 성분(SCC) 찾기: 코사라주 알고리즘 구현 방법

강연결 성분(Strongly Connected Components)이란?

방향 그래프(directed graph)에서 한 컴포넌트에 속한 모든 정점 쌍 사이에 서로 도달할 수 있는 경로가 존재할 때, 그 컴포넌트를 강연결 성분(Strongly Connected Component, SCC)이라고 합니다.

C++로 그래프의 강연결 성분(SCC) 찾기: 코사라주 알고리즘 구현 방법

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

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

입력: 그래프의 인접 행렬(adjacency matrix)

00110
10000
01000
00001
00000

출력: 주어진 그래프의 강연결 성분은 다음과 같습니다.

0 1 2
3
4

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

알고리즘

1. traverse(graph, start, visited)

입력: 탐색할 그래프, 시작 정점, 각 노드의 방문 여부 플래그
출력: DFS 방식으로 그래프의 노드를 순회하며 방문한 노드를 출력합니다.

시작
    start를 방문 처리한다
    start에 연결된 모든 정점 v에 대해 반복한다
        v를 아직 방문하지 않았다면
            traverse(graph, v, visited)를 재귀 호출한다
    반복 종료
종료

2. topoSort(u, visited, stack)

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

시작
    u를 방문 처리한다
    u에 연결된 모든 노드 v에 대해 반복한다
        v를 아직 방문하지 않았다면
            topoSort(v, visited, stack)을 재귀 호출한다
    반복 종료
    u를 스택에 push한다
종료

3. getStrongConComponents(graph)

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

시작
    처음에 모든 노드를 방문하지 않은 상태로 설정한다
    그래프의 모든 정점 i에 대해 반복한다
        i를 아직 방문하지 않았다면
            topoSort(i, vis, stack)을 호출한다
    반복 종료
    모든 노드를 다시 방문하지 않은 상태로 초기화한다
    transGraph := 주어진 그래프의 전치 그래프
    스택이 빌 때까지 반복한다
        스택에서 노드를 pop하여 v에 저장한다
        v를 아직 방문하지 않았다면
            traverse(transGraph, v, visited)를 호출한다
    반복 종료
종료

예제 코드 (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;      // 현재 노드를 방문 처리
    cout << u << " ";
    for(int v = 0; v<NODE; v++) {
        if(g[u][v]) {
            if(!visited[v])
                traverse(g, v, visited);   // 인접한 미방문 노드로 DFS 진행
        }
    }
}

void topoSort(int u, bool visited[], stack<int> &stk) {
    visited[u] = true;      // 노드 u를 방문 처리
    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {   // u에 인접한 모든 정점 v에 대해
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u);            // 시작 정점을 스택에 push
}

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 << "주어진 그래프의 강연결 성분은 다음과 같습니다:" << endl;
    getStrongConComponents();
}

실행 결과

주어진 그래프의 강연결 성분은 다음과 같습니다:
0 1 2
3
4

마무리

이 프로그램은 코사라주 알고리즘을 이용해 방향 그래프의 강연결 성분을 구합니다. DFS를 두 번 수행하므로 이론적 시간 복잡도는 O(V + E)입니다. 다만 위 구현은 인접 행렬을 사용하기 때문에 실질적으로 O(V²)의 비용이 드는데, 인접 리스트로 바꾸면 희소 그래프에서도 선형 시간에 가깝게 처리할 수 있습니다.