スターグラフの判定方法：隣接行列を用いたアルゴリズムとC++実装例

グラフが与えられたとき、そのグラフがスターグラフ（star graph）であるかどうかを判定する問題について解説します。スターグラフとは、1つの中心頂点（ハブ）が他のすべての頂点に接続され、周辺の頂点同士は互いに接続されていない木構造の一種で、全体の形が星のように見えることからこの名前が付いています。

判定には、グラフを走査して「次数が1の頂点の個数」と「次数が n−1 の頂点の個数」を数えます（ここで n はグラフの頂点数です）。次数1の頂点が n−1 個存在し、かつ次数 n−1 の頂点がちょうど1個存在する場合、そのグラフはスターグラフであると判定できます。

入力と出力

入力（隣接行列）:
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0

出力:
It is a star graph.

アルゴリズム

判定を行う関数 checkStarGraph(graph) の擬似コードは以下の通りです。

入力: 判定対象のグラフ

出力: スターグラフであれば true、そうでなければ false

Begin
    degOneVert := 0, degNminOneGraph := 0
    if グラフの頂点数が1の場合
        自己ループがなければ true を返す
    else if グラフの頂点数が2の場合
        2頂点間に辺が1本だけあれば true を返す
    else
        グラフ内のすべての頂点 i について繰り返す
            degree := 0
            頂点 i に隣接するすべての頂点 j について繰り返す
                degree := degree + 1
            done
            if degree = 1 ならば
                degOneVert := degOneVert + 1
            else if degree = n-1 ならば
                degNminOneGraph := degNminOneGraph + 1
            done
        done

    if degOneVert = n-1 かつ degNminOneGraph = 1 ならば
        true を返す
    それ以外は false を返す
End

C++による実装例

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

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

bool checkStarGraph() {
    int degOneVert = 0, degVert = 0;     //初期値：次数1の頂点数、次数n-1の頂点数はともに0
    if (NODE == 1)     //頂点が1つだけの場合
        return (graph[0][0] == 0);

    if (NODE == 2)
        return (graph[0][0] == 0 && graph[0][1] == 1 && graph[1][0] == 1 && graph[1][1] == 0);

    for (int i = 0; i < NODE; i++) {     //頂点数が3以上のグラフに対する処理
        int degree = 0;
        for (int j = 0; j < NODE; j++)     //頂点iの次数をカウント
            if (graph[i][j])
                degree++;
        if (degree == 1)
            degOneVert++;
        else if (degree == NODE-1)
            degVert++;
    }
    //次数n-1の頂点が1つで、残りの頂点がすべて次数1のときスターグラフとなる
    return (degOneVert == (NODE-1) && degVert == 1);
}

int main() {
    if(checkStarGraph())
        cout << "It is a star graph.";
    else
        cout << "It is not a star graph.";
}

実行結果

It is a star graph.

計算量

このアルゴリズムは隣接行列を走査してすべての頂点の次数を数えるため、時間計算量は O(n²) です。また、隣接行列を保持しておく必要があるため、空間計算量も O(n²) となります。なお、隣接リストを用いて実装すれば、計算量を辺の数 E に比例した O(E) まで抑えることが可能です。