주어진 그래프가 트리인지 판별하는 방법

이 문제에서는 하나의 무방향 그래프(undirected graph)가 주어지며, 해당 그래프가 트리(tree)인지 아닌지를 판별해야 합니다. 트리의 기본 조건을 검사하면 비교적 간단하게 확인할 수 있습니다. 트리는 사이클(cycle)을 포함하지 않기 때문에, 그래프에 사이클이 하나라도 존재한다면 그 그래프는 트리가 아닙니다.

또 다른 접근 방식으로도 판별할 수 있습니다. 그래프가 연결 그래프이면서 간선의 개수가 V-1개(V는 그래프의 정점 수)라면, 그 그래프는 트리일 가능성이 높습니다. 즉, '사이클 없음'과 '모든 정점의 연결성' 두 가지 조건을 모두 만족하는지 검사하면 됩니다.

입력과 출력

입력:
인접 행렬(adjacency matrix)
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
1 1 1 1 0

출력:
그래프는 트리입니다(The Graph is a tree)

알고리즘

isCycle(u, visited, parent)

입력: 시작 정점 u, 방문 여부를 표시하기 위한 visited 리스트, 부모 정점(parent).

출력: 그래프에 사이클이 존재하면 true.

Begin
    u를 방문한 것으로 표시
    u와 인접한 모든 정점 v에 대해 반복:
        if v를 아직 방문하지 않았다면:
            if isCycle(v, visited, u) = true, then
                return true
        else if v ≠ parent, then
            return true
    return false
End

isTree(graph)

입력: 무방향 그래프.

출력: 그래프가 트리이면 true.

Begin
    방문 여부를 저장할 visited 배열을 정의
    처음에는 모든 노드를 방문하지 않은 상태로 초기화
    if isCycle(0, visited, φ) = true, then //시작 정점의 부모는 null
        return false
    if 그래프가 연결되어 있지 않다면, then
        return false
    그 외의 경우 return true
End

예제 코드 (C++)

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

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

bool isCycle(int u, bool visited[], int parent) {
    visited[u] = true;          //u를 방문한 것으로 표시
    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v]) {   //인접 노드 v를 아직 방문하지 않은 경우
                if(isCycle(v, visited, u)) {
                    return true;
                }
            } else if(v != parent) { //방문했지만 부모 정점이 아닌 경우
                return true;         //사이클이 존재함
            }
        }
    }
    return false;
}

bool isTree() {
    bool *vis = new bool[NODE];

    for(int i = 0; i<NODE; i++)
        vis[i] = false;             //아직 어떤 노드도 방문하지 않은 상태로 초기화

    if(isCycle(0, vis, -1))         //사이클 존재 여부 검사
        return false;

    for(int i = 0; i<NODE; i++) {
        if(!vis[i])                 //탐색에서 방문하지 못한 노드가 있다면 그래프는 연결되어 있지 않음
            return false;
    }
    return true;
}

int main() {
    if(isTree())
        cout << "The Graph is a Tree.";
    else
        cout << "The Graph is not a Tree.";
}

실행 결과

The Graph is a Tree.

정리

이 알고리즘은 깊이 우선 탐색(DFS)을 활용하여 두 가지 핵심 조건을 검사합니다. 첫째, 탐색 과정에서 부모 정점이 아닌 이미 방문한 정점을 다시 만나면 사이클이 존재하므로 트리가 아닙니다. 둘째, 사이클이 없더라도 탐색 후 방문되지 않은 정점이 남아 있다면 그래프가 연결되어 있지 않다는 뜻이므로 역시 트리가 아닙니다. 이 두 조건을 모두 통과해야만 주어진 그래프를 트리로 판별할 수 있으며, 시간 복잡도는 정점 수와 간선 수에 비례하는 O(V + E)입니다.