【アルゴリズム・データ構造】方向を持たない頂点と辺で構成されたネットワーク！「無向グラフ」｜情報処理問題1000本ノック
基本情報技術者試験、応用情報技術者試験のアルゴリズム・データ構造（グラフ理論）分野で基本となる重要用語。「無向グラフ（Undirected Graph）」の性質と、隣接行列によるデータ表現方法を攻略しましょう。
1. 【 問題 】：テクノロジ系（アルゴリズム・グラフ理論）
【 問題 】 グラフ理論におけるデータ構造に関する記述です。すべての辺（エッジ）が方向や順序関係を持たない無向エッジで構成されており、接続された頂点（ノード）間を双方向に相互移動することができるグラフ構造は、次のうちどれか。
（ア）有向グラフ（Directed Graph / Digraph）
（イ）無向グラフ（Undirected Graph）
（ウ）完全二分木（Complete Binary Tree）
（エ）DAG（Directed Acyclic Graph）
2. 正解：
正解：（イ）無向グラフ（Undirected Graph）
3. 解説：「『双方通行の網の目』＝対称性を持つグラフ構造！」
無向グラフは、頂点間の結びつきに対称性（$A$から$B$に行けるなら、$B$から$A$にも行ける）があるネットワークを表現するのに最適なデータ構造です。
プログラミングやアルゴリズムで表現する際、隣接行列（Adjacency Matrix）で表すと対角線を挟んで対比が「線対称（対称行列）」になるという重要な数学的特徴があります。
| グラフの種類 | エッジの特徴 | 隣接行列の性質 | 代表的な適用例 |
|---|---|---|---|
| （イ）無向グラフ | すべての辺に矢印（方向）がない。 | 行列が「線対称（対称行列）」になる。 （$A_{ij} = A_{ji}$） |
路線図（双方向運転）、SNSの相互友達関係、電気回路網 |
| （ア）有向グラフ | 辺に矢印（方向）がある。 | 非対称になることが多い。 （一方向のみの接続があるため） |
Webページのハイパーリンク構造、タスクの依存関係（PERT図）、一方通行路 |
1. 理解のコツ:
・「路線図」で「A駅とB駅の間を電車が往復している」状態が無向グラフです。
・一方、「一方通行の道路網」や「タスクの処理順序（Aが終わらないとBができない）」は有向グラフで表現します。
2. 試験対策の視点:
・問題文に「無向エッジからなる」「方向を持たない辺で構成」「双方向に移動可能」「隣接行列が対角線に対して対称」と出たら、迷わず無向グラフを選択しましょう！
4. まとめ
すべての辺が方向を持たない無向エッジで構成され、接続された頂点間を双方向に辿ることができるデータ構造。これが無向グラフです。矢印で進行方向が指定される有向グラフとの相違点を含めて、確実にマスターしておきましょう！