DFS를 사용해 방향 그래프가 트리인지 확인하는 C++ 프로그램

그래프(graph)는 사이클(cycle)을 하나도 포함하지 않을 때 트리(tree)라고 할 수 있습니다. 이번 글에서는 DFS(깊이 우선 탐색)을 활용하여 주어진 방향 그래프(directed graph)가 트리인지 아닌지 판별하는 C++ 프로그램을 소개합니다.

핵심 개념

방향 그래프가 트리이기 위해서는 그래프 안에 어떤 사이클도 존재해서는 안 됩니다. DFS로 그래프를 탐색하는 도중, 현재 재귀 스택에 들어 있는 정점을 다시 만나는 경우(백 엣지, back edge)가 발생하면 사이클이 있다는 뜻이며, 이러한 그래프는 트리가 될 수 없습니다.

알고리즘

시작
함수 cyclicUtil() :
    a) 현재 노드를 방문 처리하고, 재귀 스택의 일부로 표시한다.
    b) 현재 정점에 인접한 모든 정점에 대해 재귀적으로 탐색한다.
    c) 탐색이 끝나면 해당 정점을 재귀 스택에서 제거한다.
함수 cyclic() :
    a) 모든 정점을 '미방문'이면서 '재귀 스택 미포함' 상태로 초기화한다.
    b) 분리된 트리 구성 요소 속에서도 사이클을 찾을 수 있도록 CyclicUtil() 함수를 호출한다.
끝

C++ 코드 예제

#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class G {
    int n;
    list<int> *adj; // 인접 리스트 저장
    bool CyclicUtil(int v, bool visited[], bool *rs);
public:
    G(int V); // 생성자
    void addEd(int v, int w);
    bool cyclic();
};
G::G(int n) {
    this->n = n;
    adj = new list<int> [n];
}
void G::addEd(int v, int u) // 그래프에 간선 추가 {
    adj[v].push_back(u); // v의 리스트에 u 추가
}
bool G::CyclicUtil(int v, bool visited[], bool *recurS) {
    if (visited[v] == false) {
        visited[v] = true; // 현재 노드를 방문 처리하고 재귀 스택에 포함
        recurS[v] = true;
        // 현재 정점에 인접한 모든 정점에 대해 재귀 호출
        list<int>::iterator i;
        for (i = adj[v].begin(); i != adj[v].end(); ++i) {
            if (!visited[*i] && CyclicUtil(*i, visited, recurS))
                return true;
            else if (recurS[*i])
                return true;
        }
    }
    recurS[v] = false; // 재귀 스택에서 정점 제거
    return false;
}
// 그래프가 트리인지 확인
bool G::cyclic() {
    // 모든 정점을 미방문 및 재귀 스택 미포함 상태로 초기화
    bool *visited = new bool[n];
    bool *recurS = new bool[n];
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        recurS[i] = false;
    }
    // 서로 다른 트리 구성 요소에서도 사이클을 감지하기 위해 CyclicUtil() 호출
    for (int i = 0; i < n; i++)
        if (CyclicUtil(i, visited, recurS))
            return true;
    return false;
}
int main() {
    G g(4);
    g.addEd(0, 2);
    g.addEd(1, 2);
    g.addEd(2, 0);
    g.addEd(3, 2);
    if (g.cyclic())
        cout << "방향 그래프는 트리가 아닙니다";
    else
        cout << "방향 그래프는 트리입니다";
    return 0;
}

출력 결과

방향 그래프는 트리가 아닙니다

동작 원리 설명

예제 그래프에는 0 → 2, 1 → 2, 2 → 0, 3 → 2 네 개의 간선이 있습니다. 이때 0 → 2 → 0 경로가 다시 시작 정점으로 돌아오므로 사이클이 존재합니다. CyclicUtil() 함수는 DFS를 수행하면서 각 정점의 방문 여부를 visited 배열로, 재귀 호출 경로上的 포함 여부를 recurS 배열로 관리합니다. 인접 정점이 아직 방문되지 않았다면 재귀 호출을 계속 진행하고, 이미 재귀 스택에 있는 정점을 다시 만나면 즉시 true를 반환하여 사이클을 보고합니다.

시간 복잡도

이 알고리즘은 모든 정점과 간선을 최대 한 번씩만 방문하므로 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 의미합니다.