応用情報技術者 予想問題｜練習問題 第14問

解説

DFS は最も最近訪問したノードから先へ進む後入れ先出しの性質を持つため、スタック（LIFO）または関数の再帰呼び出し（コールスタック）で実装するのが自然である。一方、BFS は浅い側から順に展開するためキュー（FIFO）を用いる。優先度付きキューはダイクストラ法や A* で評価関数の小さいノードから取り出す際に用いる。グラフ探索の基本アルゴリズムは計算量 O(V+E) で、トポロジカルソートや連結成分検出に発展する。