無向グラフ

2025年10月21日

無向グラフ

英語表記: Undirected Graph

概要

無向グラフは、データ構造における「グラフ構造」の一種であり、頂点（ノード）間の関係を線（辺、エッジ）で表現する際に、その辺に方向性を持たないグラフのことを指します。これは、複雑な関係性を持つデータをモデル化する「グラフ構造」を、「辺の性質」によって分類する際の最も基本的な概念の一つです。したがって、無向グラフは、データ構造（リスト, スタック, キュー, ツリー）の中でも、特に柔軟性が求められるグラフ構造の「種類」を理解する上で、欠かせない土台となります。

詳細解説

データ構造において、グラフ構造はリストやツリー構造では表現しきれない、網の目のような複雑で非階層的な関係を扱うために非常に有用です。その中でも無向グラフが担う役割は、対称的な相互関係を正確にモデリングすることにあります。

たとえば、現実世界における「友達関係」や「双方向の通信路」のように、「AからBへの関係が成立するならば、自動的にBからAへの関係も成立する」という性質を持つデータを表現する場合に無向グラフは最適です。もしこの相互性を表現できないと、データ構造としてのグラフの有用性は大きく損なわれてしまいますね。

構成要素と動作原理

無向グラフの構成要素は、データ要素そのものである「頂点（Vertex/ノード）」と、頂点間の関係を示す「辺（Edge/エッジ）」の二つです。

頂点 (V): データ構造における要素（例：人、都市、ウェブページなど）を表します。
辺 (E): 頂点間の接続や関係性を示します。

無向グラフの最も重要な特徴は、辺が順序付けられていないペア ${u, v}$ として定義される点です。これは、辺が頂点 $u$ と $v$ を結びつけているだけであり、AからBへの方向を示す矢印が存在しないことを意味します。辺が ${A, B}$ であれば、それは ${B, A}$ と完全に同等であり、データの流れや関係が常に双方向であることを保証します。

データ構造としての実装

計算機科学的には、無向グラフをメモリ上で表現する方法として、「隣接行列（Adjacency Matrix）」や「隣接リスト（Adjacency List）」がよく使われます。

隣接行列: $N \times N$ の行列で表現されます。無向グラフの場合、AとBの間に辺があれば、行列の $(A, B)$ 要素と $(B, A)$ 要素の両方に値（通常は1）が設定されます。その結果、隣接行列は必ず対称行列になります。この対称性は、無向グラフが持つ相互性の性質をデータ構造として忠実に反映している証拠であり、有向グラフ（非対称になり得る）との決定的な違いを示します。
隣接リスト: 各頂点に対して、直接接続されている頂点のリストを保持します。無向グラフでは、AのリストにBが含まれていれば、BのリストにもAが含まれている必要があります。

データ構造（リスト, スタック, キュー, ツリー）の文脈から見ると、無向グラフの存在は、我々が扱うデータが単なる線形や階層的な構造だけでなく、いかに複雑な関係性を持っているかを教えてくれます。そして、その複雑な関係を効率的に処理するための「道具」として、無向グラフは非常に重要な「種類」なのです。

具体例・活用シーン

無向グラフは、その相互性の性質から、現実世界の多くの対称的なシステムをモデル化するために利用されています。グラフ構造がどのような場面で役立つのかを知ることは、データ構造の学習において非常に楽しいポイントだと私は思います。

SNSの友達関係のモデリング
- AさんがBさんと「友達」であると定義した場合、それはBさんもAさんと友達であることを意味します。無向グラフを使えば、この相互承認の関係をシンプルかつ正確に表現できます。
物理的なネットワーク接続
- コンピューターネットワーク（LANなど）において、ケーブルで直接接続された二つの機器間の通信路が双方向である場合、無向グラフとしてモデル化できます。
学術論文の共著者関係
- 二人の研究者が共同で論文を執筆した場合、その関係は対称的です。誰が先に、後に執筆したかという方向性を無視し、単に「関係がある」ことだけを表現します。

【初心者のための比喩：迷宮の双方向扉】

無向グラフを理解するための比喩として、「双方向に開く扉を持つ迷宮」を想像してみてください。

この迷宮にはたくさんの部屋（頂点）があり、部屋同士は扉（辺）で結ばれています。無向グラフの重要な点は、すべての扉が双方向に開くという点です。もし部屋Aと部屋Bの間に扉があれば、あなたはAからBへ進むことができますし、BからAへ戻ることもできます。

これに対し、もし扉が「有向グラフ」のように一方通行だった場合、BからAへは戻れず、迷宮の構造が全く変わってしまいます。データ構造における「グラフの種類」とは、このように、データの繋がりが持つ「方向性」によって、その構造や利用方法が根本的に変化することを教えてくれるのです。無向グラフは、いつでも戻れる安心感のある、信頼性の高い繋がりを表現するのに適していると言えますね。

資格試験向けチェックポイント

無向グラフに関する知識は、IT Passport、基本情報技術者試験、応用情報技術者試験のいずれにおいても、データ構造やアルゴリズムの基礎知識として問われます。特に「グラフの種類」の区別は得点源になりやすいポイントです。

最重要ポイント：有向グラフとの区別
- 試験では、「特定の関係性（例：一方的なフォロー関係、一方通行の道路）を表現するのに適したグラフは何か」といった形で、無向グラフと有向グラフ（Directed Graph）の違いを問われます。辺に方向性がないのが無向グラフ、矢印で方向が示されているのが有向グラフである、という根本的な違いを必ず理解しておきましょう。
頂点の次数 (Degree)
- 無向グラフでは、ある頂点に接続されている辺の総数を「次数」と呼びます。有向グラフのような「入次数」「出次数」の区別は不要です。この「次数」は、グラフの基本的な性質を問う問題（特に基本情報技術者試験）で頻繁に登場します。次数が大きいほど、その頂点がデータ構造内で多くの要素と関係を持っていることを示します。
連結性の概念
- 無向グラフでは、すべての頂点が辺によって繋がっている状態を「連結（Connected）」と呼びます。グラフの探索アルゴリズム（深さ優先探索 DFS、幅優先探索 BFS）を適用する際、グラフが連結であるかどうかが前提となることが多いため、この概念の定義をしっかりと押さえておく必要があります。
適用アルゴリズム
- 無向グラフ上で効率的に動作する重要なアルゴリズムとして、最小全域木（Minimum Spanning Tree, MST）を求めるプリム法（Prim’s algorithm）やクラスカル法（Kruskal’s algorithm）があります。これらのアルゴリズムは、通信網や配管網など、双方向の接続コストを最小化したい場面で利用され、応用情報技術者試験では具体的な手順や計算量が問われることがあります。