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

C++로 무방향 그래프의 연결 요소 찾기: DFS 기반 강연결·약연결 판별 프로그램

DFS(깊이 우선 탐색)를 활용하면 주어진 무방향 그래프가 약연결(weakly connected) 상태인지 강연결(strongly connected) 상태인지 판별할 수 있습니다. 이 글에서는 그래프의 강연결 요소(SCC)를 찾아 연결 상태를 확인하는 C++ 프로그램을 소개합니다.

핵심 개념 정리

강연결은 그래프의 모든 정점 쌍이 서로 도달 가능한 경우를 말하며, 약연결은 간선의 방향을 무시했을 때만 전체가 하나로 이어지는 경우를 말합니다. 이 프로그램은 코사라주(Kosaraju) 알고리즘을 응용하여 강연결 요소의 개수를 센 뒤, 개수가 1이면 강연결, 2개 이상이면 약연결로 판정합니다.

알고리즘에 사용되는 함수

시작
함수 fillOrder(): 스택에 모든 정점을 채운다.
    a) 현재 노드를 방문 처리하고 출력한다.
    b) 이 정점에 인접한 모든 정점에 대해 재귀 호출한다.
    c) v에서 도달 가능한 모든 정점이 처리되면 v를 스택에 push한다.
종료

시작
함수 DFS():
    a) 현재 노드를 방문 처리하고 출력한다.
    b) 이 정점에 인접한 모든 정점에 대해 재귀 호출한다.
종료

C++ 예제 코드

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class G {
    int m;
    list<int> *adj;
    // 함수 선언
    void fillOrder(int n, bool visited[], stack<int> &Stack);
    void DFS(int n, bool visited[]);
public:
    G(int N);          // 생성자
    void addEd(int v, int w);
    int print();
    G getTranspose();
};

G::G(int m) {
    this->m = m;
    adj = new list<int>[m];
}

// 깊이 우선 탐색 수행
void G::DFS(int n, bool visited[]) {
    visited[n] = true;              // 현재 노드를 방문 처리하고 출력
    cout << n << " ";
    list<int>::iterator i;
    // 이 정점에 인접한 모든 정점에 대해 재귀 호출
    for (i = adj[n].begin(); i != adj[n].end(); ++i)
        if (!visited[*i])
            DFS(*i, visited);
}

// 그래프의 전치(transpose) 그래프 생성
G G::getTranspose() {
    G g(m);
    for (int n = 0; n < m; n++) {
        list<int>::iterator i;
        for (i = adj[n].begin(); i != adj[n].end(); ++i) {
            g.adj[*i].push_back(n);
        }
    }
    return g;
}

// 간선 추가
void G::addEd(int v, int w) {
    adj[v].push_back(w);            // v의 리스트에 w 추가
}

// 종료 순서대로 정점을 스택에 채우는 함수
void G::fillOrder(int v, bool visited[], stack<int> &Stack) {
    visited[v] = true;              // 현재 노드를 방문 처리
    list<int>::iterator i;
    // 이 정점에 인접한 모든 정점에 대해 재귀 호출
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            fillOrder(*i, visited, Stack);
    Stack.push(v);                  // v에서 도달 가능한 정점 처리 후 push
}

// 강연결 요소를 출력하고 개수를 반환
int G::print() {
    stack<int> Stack;
    bool *visited = new bool[m];
    for (int i = 0; i < m; i++)
        visited[i] = false;

    // 첫 번째 DFS: 종료 순서대로 스택에 정점 저장
    for (int i = 0; i < m; i++)
        if (visited[i] == false)
            fillOrder(i, visited, Stack);

    G graph = getTranspose();       // 뒤집힌(전치) 그래프 생성

    for (int i = 0; i < m; i++)     // 모든 정점을 미방문 상태로 초기화
        visited[i] = false;

    int count = 0;
    // 스택에 저장된 순서대로 정점을 처리
    while (Stack.empty() == false) {
        int v = Stack.top();
        Stack.pop();                // 스택에서 정점 꺼내기
        if (visited[v] == false) {
            graph.DFS(v, visited);  // 전치 그래프에서 DFS 수행
            cout << endl;
        }
        count++;
    }
    return count;
}

int main() {
    G g(5);
    g.addEd(2, 1);
    g.addEd(3, 2);
    g.addEd(1, 0);
    g.addEd(0, 3);
    g.addEd(3, 1);

    cout << "다음은 주어진 그래프의 강연결 요소입니다\n";
    if (g.print() > 1) {
        cout << "그래프는 약연결(weakly connected) 상태입니다.";
    } else {
        cout << "그래프는 강연결(strongly connected) 상태입니다.";
    }
    return 0;
}

실행 결과

다음은 주어진 그래프의 강연결 요소입니다
4
0 1 2 3
그래프는 약연결(weakly connected) 상태입니다.

동작 원리 살펴보기

위 프로그램은 다음 세 단계로 동작합니다.

  1. 첫 번째 DFS 수행: 원본 그래프에서 DFS를 진행하며, 탐색이 종료된 정점부터 스택에 차례로 push합니다.
  2. 그래프 전치: 모든 간선의 방향을 뒤집은 전치 그래프를 만듭니다.
  3. 두 번째 DFS 수행: 스택에서 정점을 하나씩 꺼내며 아직 방문하지 않은 정점에 대해 전치 그래프에서 DFS를 수행합니다. 이때 한 번의 DFS로 방문되는 정점들의 집합이 곧 하나의 강연결 요소(SCC)입니다.

예제 그래프에서 정점 4는 어떤 간선과도 연결되어 있지 않아 단독 요소 {4}를 이루고, 나머지 정점 {0, 1, 2, 3}은 서로 도달 가능한 하나의 요소를 이룹니다. 따라서 강연결 요소가 총 2개이므로 이 그래프는 약연결 상태로 판정됩니다.

시간 복잡도

이 알고리즘은 DFS를 두 번 수행하고 그래프 전치 역시 선형 시간에 처리하므로, 정점 V개, 간선 E개 기준 전체 시간 복잡도는 O(V + E)입니다.