C++로 방향 그래프의 연결 여부 확인하기

그래프의 연결성을 확인하려면 임의의 그래프 탐색 알고리즘을 사용하여 모든 노드를 방문해 봅니다. 탐색이 종료된 후에도 방문하지 않은 노드가 하나라도 남아 있다면, 해당 그래프는 연결되어 있지 않다고 판단할 수 있습니다.

방향 그래프(directed graph)의 경우에는 모든 정점을 시작점으로 삼아 각각 탐색을 수행해야 합니다. 어떤 정점은 나가는 간선(outgoing edge)만 존재하고 들어오는 간선(incoming edge)이 없을 수 있기 때문에, 다른 노드에서 출발한 탐색만으로는 해당 정점에 도달할 수 없습니다.

여기서 사용하는 탐색 알고리즘은 재귀 방식의 DFS(깊이 우선 탐색)입니다.

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

출력 − 그래프가 연결되어 있습니다.

알고리즘

traverse(u, visited)
입력: 시작 노드 u와 방문 여부를 기록하는 visited 배열
출력: 연결된 모든 정점을 탐색합니다.
시작
    u를 방문한 것으로 표시
    u와 인접한 모든 정점 v에 대해 반복
        v를 아직 방문하지 않았다면
            traverse(v, visited) 호출
    종료
끝

isConnected(graph)
입력: 그래프
출력: 그래프가 연결되어 있으면 true
시작
    visited 배열 선언
    그래프의 모든 정점 u에 대해 반복
        모든 노드를 미방문 상태로 초기화
        traverse(u, visited) 호출
        아직 방문하지 않은 노드가 남아 있다면
            false 반환
    종료
    true 반환
끝

예제 코드

#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]){ // 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 << "그래프가 연결되어 있습니다.";
    else
    cout << "그래프가 연결되어 있지 않습니다.";
}

실행 결과

그래프가 연결되어 있습니다.

위 코드는 각 정점을 시작점으로 DFS를 수행한 뒤, 모든 노드를 방문했는지 검사하는 방식입니다. 시간 복잡도는 정점의 개수를 V라 할 때 O(V × (V + E))이며, V개의 정점 각각에 대해 DFS가 한 번씩 실행되기 때문입니다. 이 방식은 사실상 그래프가 강하게 연결(strongly connected)되어 있는지를 판별하는 것과 같으며, 더 효율적인 방법으로는 코사라주(Kosaraju) 알고리즘이나 타잔(Tarjan) 알고리즘을 활용할 수 있습니다.