C++で木グラフ（ツリーグラフ）が線形かどうかを判定する方法

本記事では、C++を使って与えられた木グラフ（ツリーグラフ）が「線形（リニア）」であるかどうかを判定する方法を解説します。線形の木グラフとは、すべてのノード（頂点）を一本の線上に連ねて表現できるグラフのことです。

線形木グラフとは

たとえば、下の図のようなグラフは一本の線で表現できるため、線形の木グラフです。

一方、次のように途中で分岐（複数の子ノード）を持つ木は線形ではありません。

線形グラフを判定する条件

ある木グラフが線形かどうかは、次の2つの条件で確認できます。

• ノード数が1の場合、その木グラフは線形である。
• n個のノードのうち (n − 2) 個のノードの次数が2である場合、その木グラフは線形である。

線形グラフでは、両端にある2つのノードの次数が1となり、それ以外の (n − 2) 個のノードの次数はすべて2になります。つまり、次数2のノードの数を数えるだけで判定が可能です。

C++による実装例

#include <iostream>
#include <vector>
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() {
        // ノード数が1なら線形
        if (V == 1)
            return true;
        // 次数が2のノードをカウント
        int count = 0;
        for (int i = 0; i < V; i++) {
            if (adj[i].size() == 2)
                count++;
        }
        return count == V - 2;
    }
};

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";

    return 0;
}

コードの解説

Graphクラスは、隣接リスト（vector<int>の配列）によってグラフを表現しています。addEdge()メソッドは無向グラフとして両方向にエッジを登録します。

isLinear()メソッドでは、まずノード数Vが1であれば即座にtrueを返します。その後、すべてのノードを走査して隣接リストのサイズ（＝次数）が2であるノードをカウントし、その数が V − 2 と一致すれば線形グラフとしてtrueを返します。

出力

The graph is linear

この例では、ノード数3のグラフに対してエッジ(0, 1)と(0, 2)が追加されています。これは「1 − 0 − 2」という一本のパスを形成しており、中央のノード0の次数が2、両端のノード1と2の次数が1となるため、プログラムは「The graph is linear」を出力します。

まとめ

この判定方法は、全ノードの次数を一度だけ走査すればよいため、時間計算量はO(V)と非常に効率的です。木構造がリンクリストのように鎖状につながっているかどうかを確認したい場合に活用できる手法です。