グラフ（基礎）BFS, DFS

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Redundant Connection （Time Complexity: $\mathrm{O(N^2)}$）	★★	高	BFS, DFS
Detonate the Maximum Bombs	★★★	高	BFS, DFS
All Nodes Distance K in Binary Tree	★★★	中	BFS, DFS
Reconstruct Itinerary	★★★★	中	DFS

本章ではBFSとDFSについて改めて確認していきます。二分木のセクションのBFSとDFSを学んでいることを前提としていますので、まだ曖昧な方は一旦そちらを復習しておきましょう。

BFSおよびDFSは 時間計算量: $\mathrm{O(N+E)}$、 空間計算量: $\mathrm{O(N)}$で全てのノードを探索する手法です。（グラフのBFSとDFSでは基本的には隣接リストを使用するためです。）

N: グラフのノード数、E: グラフのエッジ数。

BFS

まずは二分木でのBFSの基本コードをおさらいしましょう。以下の様にノードの左の子と右の子をみてキューに追加していることがわかります。