LeetCode 練習問題集
問題 | 難易度 | 重要度 | テクニック |
Redundant Connection （Time Complexity: ） | ★★ | 高 | BFS, DFS |
★★★ | 高 | BFS, DFS | |
★★★ | 中 | BFS, DFS | |
★★★★ | 中 | DFS |
本章ではBFSとDFSについて改めて確認していきます。二分木のセクションのBFSとDFSを学んでいることを前提としていますので、まだ曖昧な方は一旦そちらを復習しておきましょう。
BFSおよびDFSは時間計算量: 、空間計算量: で全てのノードを探索する手法です。（グラフのBFSとDFSでは基本的には隣接リストを使用するためです。）
N: グラフのノード数、E: グラフのエッジ数。
BFS
まずは二分木でのBFSの基本コードをおさらいしましょう。以下の様にノードの左の子と右の子をみてキューに追加していることがわかります。
