【アルゴリズム・データ構造】矢印（方向）を持つ頂点と辺で構成されたネットワーク！「有向グラフ」｜情報処理問題1000本ノック
基本情報技術者試験、応用情報技術者試験、高度試験のアルゴリズム・データ構造（グラフ理論）分野で極めて高頻出の重要概念。「有向グラフ（Directed Graph）」の定義と、前回学習した「無向グラフ」との比較、および実社会での適用例を攻略しましょう。
1. 【 問題 】：テクノロジ系（アルゴリズム・データ構造）
【 問題 】 グラフ理論におけるデータ構造に関する記述です。頂点（ノード）同士を結ぶ辺（エッジ）に向き（順序関係）が指定されており、指定された方向にのみ辿ることができる構造を持つグラフは、次のうちどれか。
（ア）無向グラフ（Undirected Graph）
（イ）有向グラフ（Directed Graph）
（ウ）完全グラフ（Complete Graph）
（エ）二部グラフ（Bipartite Graph）
2. 正解：
正解：（イ）有向グラフ（Directed Graph）
3. 解説：「『一方通行や手順・依存関係』を表現する基本構造！」
有向グラフは、エッジ（辺）が矢印の形をしており、起点（始点）から終点への方向を持ちます。
順序関係や依存関係が存在するデータ構造をモデル化する際に幅広く使われます。
| 項目 | （イ）有向グラフ | （ア）無向グラフ |
|---|---|---|
| エッジ（辺）の性質 | 向き（矢印）がある | 向き（矢印）がない |
| 移動のルール | 矢印の方向にのみ進行可能 | 双方向に自由移動可能 |
| 隣接行列の性質 | 非対称行列になることが多い | 対称行列になる（$A_{ij} = A_{ji}$） |
| 代表的な適用例 | Webのリンク構造、タスク依存（PERT図）、一方通行路 | SNSの友達関係、路線図（双方向） |
1. 理解のコツ:
・「一方通行の道路網」や「タスクAが終わってからタスクBを進める（作業手順）」のように、**「順序や向き」が決まっているネットワーク**を描く時はすべて有向グラフになります。
2. 試験対策の視点:
・問題文に「ノード間の関係に向きがある」「矢印付きのエッジ」「一方通行」「順序関係」と来たら、迷わず有向グラフを選択しましょう！
・有向グラフの中でも、閉路（サイクル）を持たないものをDAG（Directed Acyclic Graph：有向非巡回グラフ）と呼び、ジョブスケジュール管理などで非常に重要な応用知識となります。
4. まとめ
頂点間のエッジに向き（順序関係）が存在し、一方通行の移動をモデル化するデータ構造。これが有向グラフです。向きを持たない「無向グラフ」との違いを隣接行列の性質も含めてしっかり整理しておきましょう！