Pythonでスターグラフの中心ノードを見つけるプログラム

スターグラフとは

スターグラフ（スター・グラフ）とは、1つの中心ノードと、その中心ノードを他のすべてのノードに接続するちょうど n - 1 本の辺から構成される無向グラフです。n 個のノードには 1 から n までのラベルが付けられています。

この記事では、与えられたスターグラフの中心ノードを見つけるプログラムを Python で実装します。

例えば、次のようなグラフが入力として与えられた場合を考えてみましょう。

この場合、ノード 3 がすべての辺に共通して現れる中心であるため、出力は 3 となります。

解法のアプローチ

スターグラフの性質上、中心ノードはすべての辺に出現します。一方、それ以外のノードはそれぞれ 1 本の辺にしか現れません。この性質を利用すると、非常にシンプルなアルゴリズムで中心を見つけられます。

手順は以下の通りです。

• これまでに登場したノードを記録するための空の集合（set）seen を用意します。
• グラフ内の各辺 (u, v) について以下を繰り返します。
  • u がすでに seen に存在する場合、u が中心なので u を返します。
  • v がすでに seen に存在する場合、v が中心なので v を返します。
  • いずれでもなければ、u と v を seen に追加します。

2 番目の辺を処理した時点で、必ず中心ノードが再登場するため、最悪でも 2 回のループで答えが得られます。計算量は O(1)（辺の数を定数とみなす場合）または O(E) となり、非常に効率的です。

実装例

それでは、実際の Python コードを見てみましょう。

def solve(graph):
   seen = set()

   for u, v in graph:
      if u in seen:
         return u
      if v in seen:
         return v
      seen.add(u)
      seen.add(v)

graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))

入力

[(1,3),(2,3),(4,3),(5,3),(6,3)]

出力

3

コードの解説

このコードでは、まず空の集合 seen を作成し、各辺の両端のノードを順番にチェックしていきます。最初の辺 (1, 3) を処理すると、seen は {1, 3} になります。次の辺 (2, 3) を処理する際、v = 3 がすでに seen に存在するため、即座に 3 を返します。

このように、同じノードが複数の辺に現れた時点で、そのノードが中心であると判断できるのがポイントです。スターグラフでは中心以外のノードは一度しか現れないため、この判定は常に正しく機能します。

まとめ

スターグラフの中心を見つける問題は、「中心ノードだけが複数の辺に現れる」というグラフの構造的な特徴を理解すれば、集合を使ったシンプルな走査で効率よく解決できます。グラフの全ノードや次数を数える必要もなく、最小限のコードで実装できるのが魅力です。