有向グラフと無向グラフの違いを解説
有向グラフ（ダイグラフ）と無向グラフを比較します。辺の表現、ユースケース、次数の定義、各タイプでのアルゴリズムの動作の違いを学びます。
Graph Types
詳細な説明
有向グラフ vs 無向グラフ
有向グラフと無向グラフの区別は、グラフ理論の最も基本的な概念の一つです。辺の解釈方法を決定し、適用可能なアルゴリズムに大きな影響を与えます。
無向グラフ
無向グラフでは、すべての辺が双方向です。AとBの間に辺がある場合、AからBへもBからAへも移動できます。
次数 = ノードに接続された辺の総数
有向グラフ（ダイグラフ）
有向グラフでは、辺に方向があります。AからBへの辺（A → B）は、BからAへの辺を意味しません。
入次数 = 入ってくる辺の数。出次数 = 出ていく辺の数。
アルゴリズムの違い
| 特徴 | 無向 | 有向 |
|---|---|---|
| 連結性 | 連結 / 非連結 | 強連結 / 弱連結 |
| サイクル検出 | 親以外への後退辺 | DFS木での後退辺 |
| トポロジカルソート | 適用不可 | DAGのみ |
| 最短経路 | BFS（重みなし） | BFSまたはDijkstra |
適切なタイプの選択
無向は相互関係に使用：友人関係、双方向道路、類似性ネットワーク。有向は一方向の関係に使用：Webリンク、依存関係、フォロワーグラフ、ワークフローDAG。
ユースケース
FacebookのようなSNSは友人関係を無向辺でモデル化し、Twitter/Xはフォローを有向辺でモデル化します。パッケージマネージャの依存関係グラフは有向です。道路ネットワークは双方向道路に無向、一方通行に有向を使用します。