C++로 트리 그래프가 선형인지 판별하는 방법

이 글에서는 주어진 트리 그래프가 선형(linear)인지 아닌지 확인하는 방법을 알아봅니다. 선형 트리 그래프란 모든 노드를 하나의 직선 위에 나열해 표현할 수 있는 그래프를 의미합니다.

다음은 선형 트리 그래프의 예시입니다.

반면, 아래와 같은 그래프는 선형이 아닙니다.

선형 트리 그래프의 판별 조건

그래프가 선형인지 확인하려면 다음 두 가지 조건 중 하나를 만족하는지 검사하면 됩니다.

• 노드의 개수가 1개라면 해당 트리 그래프는 선형입니다.
• n개의 노드 중 (n − 2)개 노드의 차수(degree)가 2라면 선형입니다. 이때 나머지 두 노드는 반드시 차수가 1이어야 합니다.

즉, 선형 트리는 양 끝의 두 노드만 차수가 1이고, 나머지 내부 노드들은 모두 정확히 두 개의 간선과 연결되어 있어야 합니다.

C++ 예제 코드

아래 코드는 인접 리스트(adjacency list)를 사용해 그래프를 표현하고, 차수가 2인 노드의 개수를 세어 위 조건을 검사합니다.

#include <iostream>
#include <vector>
#define N 4
using namespace std;
class Graph{
    private:
    int V;
    vector<int> *adj;
    public:
    Graph(int v){
        V = v;
        adj = new vector<int>[v];
    }
    void addEdge(int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bool isLinear() {
        if (V == 1)
            return true;
        int count = 0;
        for (int i = 0; i < V; i++) {
            if (adj[i].size() == 2)
            count++;
        }
        if (count == V - 2)
            return true;
        else
            return false;
    }
};
int main() {
    Graph g1(3);
    g1.addEdge(0, 1);
    g1.addEdge(0, 2);
    if (g1.isLinear())
        cout << "The graph is linear";
    else
        cout << "The graph is not linear";
}

코드 동작 원리

• Graph 클래스는 정점 개수(V)와 각 정점의 인접 정점 목록을 저장하는 벡터 배열로 구성됩니다.
• addEdge() 함수는 무방향 그래프이므로 양방향으로 간선 정보를 추가합니다.
• isLinear() 함수는 먼저 노드가 1개인 경우 선형으로 판단하고, 그렇지 않으면 차수가 2인 노드의 개수를 셉니다.
• 차수가 2인 노드의 개수가 전체 노드 수에서 2를 뺀 값(V − 2)과 같다면 선형 트리입니다.

실행 결과

예제의 그래프는 노드 3개(0, 1, 2)로 구성되어 있으며, 노드 0의 차수는 2, 노드 1과 2의 차수는 각각 1입니다. 따라서 차수가 2인 노드의 개수(1개)가 V − 2(1개)와 일치하므로 선형 그래프로 판별됩니다.

The graph is linear