グラフ理論とグラフ探索（幅優先探索・深さ優先探索）とは？

グラフ理論とグラフ探索（幅優先探索・深さ優先探索）とは、ノード（頂点）と、それらをつなぐエッジ（辺）からなるデータ構造をグラフという。グラフを探索する代表的な方法に、近いノードから順に幅広く調べる幅優先探索（BFS）と、行けるところまで深く進んでから戻る深さ優先探索（DFS）がある。

ぐらふりろんとぐらふたんさく

基本情報技術者試験の頻出用語／テクノロジ系／別名：グラフ理論とグラフ探索、幅優先探索・深さ優先探索、幅優先探索、深さ優先探索

グラフ理論とグラフ探索（幅優先探索・深さ優先探索）の意味

ノード（頂点）と、それらをつなぐエッジ（辺）からなるデータ構造をグラフという。グラフを探索する代表的な方法に、近いノードから順に幅広く調べる幅優先探索（BFS）と、行けるところまで深く進んでから戻る深さ優先探索（DFS）がある。

路線図の駅間の最短乗換回数を求めるにはBFSが適しており、迷路の全経路を漏れなく調べたい場合はDFSが用いられることが多い。

BFSはキュー（FIFO）、DFSはスタック（LIFO）またはその考え方に基づく再帰で実装されるという対応関係が問われやすい。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。