グラフとは？

詳細解説

グラフ（Graph）は、頂点（Vertex/Node）と頂点間を結ぶ辺（Edge）の集合からなるデータ構造で、ものとものの関係性を表現します。木構造はグラフの特殊形（ループのない連結グラフ）です。分類：有向グラフ（辺に方向がある、例：Webページのリンク）vs 無向グラフ（方向なし、例：友人関係）、重み付きグラフ（辺にコスト/距離がある、例：地図）vs 重みなしグラフ。特殊なグラフ：DAG（有向非巡回グラフ：サイクルのない有向グラフ、タスク依存関係の表現に使用）。グラフの探索アルゴリズム：BFS（幅優先探索：最短経路の探索）、DFS（深さ優先探索：経路の存在確認・トポロジカルソート）。最短経路アルゴリズム：ダイクストラ法（非負の重みを持つ重み付きグラフの単一始点最短経路、O((V+E)log V)）。FE試験では「グラフ構造の概念（頂点・辺）」「BFS/DFSの探索順序のトレース」が出題ポイントです。ネットワーク（トポロジー）設計やSNSの友人関係もグラフ構造の実例です。

FE試験での出題ポイント

• 1有向・無向、重み付き・重みなしの4種類の分類
• 2BFS（幅優先）：キューを使って同じ深さを横断→最短経路探索に使う
• 3DFS（深さ優先）：スタック（または再帰）を使って深く探索→経路存在確認
• 4ダイクストラ法：非負の重み付きグラフの最短経路（FE上級問題）

関連用語