유향 그래프의 연결성 검사: DFS 탐색 알고리즘으로 구현하기

그래프의 연결성(connectivity)을 확인하는 기본 원리는 간단합니다. 임의의 탐색 알고리즘을 사용해 그래프의 모든 노드를 순회해 보고, 탐색이 끝난 후에도 방문되지 않은 노드가 하나라도 남아 있다면 그 그래프는 연결되어 있지 않다고 판단합니다.

다만 유향 그래프(directed graph)의 경우에는 무향 그래프와 달리 주의가 필요합니다. 특정 노드가 나가는 간선(outward edge)만 존재하고 들어오는 간선(inward edge)이 없다면, 다른 노드에서 탐색을 시작했을 때 해당 노드에 도달할 수 없습니다. 따라서 유향 그래프에서는 모든 노드를 시작점으로 삼아 각각 탐색을 수행해야 정확한 연결성 판단이 가능합니다.

이 글에서는 이러한 검사를 위해 재귀적 DFS(깊이 우선 탐색) 알고리즘을 활용합니다.

입력 및 출력 형식

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

출력:
The Graph is connected. (그래프는 연결되어 있습니다.)

알고리즘

1. traverse(u, visited)

입력: 시작 노드 u와, 방문 여부를 표시할 visited 배열.

출력: u와 연결된 모든 정점을 순회합니다.

Begin
    mark u as visited
    for all vertex v, if it is adjacent with u, do
       if v is not visited, then
          traverse(v, visited)
    done
End

이 함수는 시작 노드 u를 방문 처리한 뒤, u와 인접한 모든 정점 v 중 아직 방문하지 않은 정점에 대해 재귀적으로 탐색을 수행합니다.

2. isConnected(graph)

입력: 검사 대상 그래프.

출력: 그래프가 연결되어 있으면 true, 아니면 false.

Begin
    define visited array
    for all vertices u in the graph, do
        make all nodes unvisited
        traverse(u, visited)
        if any unvisited node is still remaining, then
            return false
    done
    return true
End

모든 정점을 시작점으로 지정하고, 각 시작점마다 visited 배열을 초기화한 후 탐색을 진행합니다. 탐색 후에도 방문되지 않은 노드가 남아 있다면 즉시 false를 반환하고, 모든 시작점에서 전체 노드를 방문했다면 true를 반환합니다.

C++ 구현 예제

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

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

void traverse(int u, bool visited[]) {
    visited[u] = true;   // 현재 노드를 방문 처리

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

bool isConnected() {
    bool *vis = new bool[NODE];
    // 모든 정점 u를 시작점으로 하여 전체 노드 방문 여부를 검사

    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i<NODE; i++)
            vis[i] = false;   // 방문 배열 초기화

        traverse(u, vis);
        for(int i = 0; i<NODE; i++) {
            if(!vis[i])   // 탐색 후에도 방문되지 않은 노드가 있으면 비연결 그래프
                return false;
        }
    }
    return true;
}

int main() {
    if(isConnected())
        cout << "The Graph is connected.";
    else
        cout << "The Graph is not connected.";
}

실행 결과

The Graph is connected.

위 예제에서 그래프는 5개의 노드로 구성되어 있으며, 어느 노드에서 탐색을 시작하더라도 나머지 모든 노드에 도달할 수 있는 구조입니다. 따라서 프로그램은 그래프가 연결되어 있다고 출력합니다.

정리

유향 그래프의 연결성 검사는 무향 그래프보다 계산량이 많습니다. 각 노드를 시작점으로 DFS를 수행해야 하므로 시간 복잡도는 O(V × (V + E))가 됩니다(V는 정점 수, E는 간선 수). 만약 강하게 연결(strongly connected) 여부만 빠르게 확인하고 싶다면 코사라주(Kosaraju) 알고리즘이나 타잔(Tarjan) 알고리즘을 활용하면 O(V + E) 시간에 검사할 수 있습니다.