DFS로 무방향 그래프가 트리인지 판별하는 C++ 프로그램

트리(tree)는 사이클(cycle)을 하나도 포함하지 않는 연결 그래프입니다. 따라서 무방향 그래프(undirected graph)가 트리인지 판별하려면 그래프 내부에 사이클이 존재하는지만 확인하면 됩니다. 이 글에서는 깊이 우선 탐색(DFS)으로 사이클을 검출하는 방식을 통해 무방향 그래프가 트리인지 확인하는 C++ 프로그램을 살펴봅니다.

동작 원리

DFS로 그래프를 순회하던 중 이미 방문한 정점을 다시 만났을 때, 그 정점이 현재 정점의 직전(부모) 정점이 아니라면 현재 정점으로 돌아오는 또 다른 경로가 존재한다는 의미이므로 사이클이 있다고 판단합니다. 반대로 모든 정점을 순회할 때까지 사이클이 발견되지 않으면 해당 그래프는 트리입니다.

알고리즘

시작
함수 cyclicUtil() :
    A) 현재 노드를 방문(visited) 처리한다.
    B) 이 정점에 인접한 모든 정점에 대해 재귀 호출한다.
    C) 인접 정점이 아직 방문되지 않았다면, 그 정점에 대해 재귀 호출한다.
    D) 인접 정점이 이미 방문되어 있고 현재 정점의 부모가 아니라면, 사이클이 존재한다.
종료
시작
함수 cyclic() :
    A) 모든 정점을 '방문하지 않음' 상태로 초기화한다.
    B) 서로 다른 DFS 트리에서 사이클을 탐지하기 위해 재귀 함수 cyclicUtil()을 호출한다.
종료

예제 코드

#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class G {
    int n;
    list<int> *adj;
    bool CyclicUtil(int v, bool visited[], int par);
public:
    G(int n); // 생성자
    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 추가
    adj[u].push_back(v); // u의 리스트에 v 추가
}
// 정점 v에서 도달 가능한 부분 그래프의 사이클을 visited[] 배열로 탐지하는 재귀 함수
bool G::CyclicUtil(int v, bool visited[], int par) {
    visited[v] = true; // 현재 노드를 방문 처리
    // 현재 정점에 인접한 모든 정점에 대해 재귀 호출
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
        // 인접 정점이 방문되지 않았다면 재귀 호출
        if (!visited[*i]) {
            if (CyclicUtil(*i, visited, v))
                return true;
        }
        // 인접 정점이 방문된 상태이면서 현재 정점의 부모가 아니라면 사이클 존재
        else if (*i != par)
            return true;
    }
    return false;
}
// 그래프가 트리인지 확인하는 함수
bool G::cyclic() {
    bool *visited = new bool[n]; // 모든 정점을 방문하지 않음으로 초기화
    for (int i = 0; i < n; i++)
        visited[i] = false;
    // 서로 다른 DFS 트리에서 사이클을 탐지하기 위해 재귀 함수 CyclicUtil() 호출
    for (int u = 0; u < n; u++)
        if (!visited[u])
            if (CyclicUtil(u, visited, -1))
                return true;
    return false;
}
int main() {
    G g1(4);
    g1.addEd(0, 1);
    g1.addEd(1, 2);
    g1.cyclic() ? cout << \"Undirected Graph isn't a tree\\n\" : cout
    << \"Undirected Graph is a tree\\n\";
    return 0;
}

실행 결과

Undirected Graph is a tree

정리

위 프로그램은 정점 4개와 간선 0-1, 1-2로 구성된 그래프를 대상으로 사이클 검사를 수행합니다. 사이클이 발견되지 않으므로 \"Undirected Graph is a tree\"가 출력됩니다. 이 방법의 시간 복잡도는 O(V+E)로, 그래프의 정점 수와 간선 수에 비례하며, 연결 요소가 여러 개인 그래프도 각 DFS 트리마다 사이클 검사를 수행해 정확하게 판별할 수 있습니다.