Time and Space Complexity
Coddyの「深さ優先探索 - グラフアルゴリズム」コースのレッスン 7/9。
時間計算量:
- O(V + E)
- 隣接リストの構築ですべてのエッジを1回走査し、探索ですべての頂点を訪問して各エッジを一定回数確認します。
空間計算量:
- O(V + E)
- 隣接リストはすべてのエッジを格納し、visited配列とスタックはそれぞれ最大V個の頂点を保持します。
まとめ:
- DFSはまず深く探索し、未訪問の隣接ノードがなくなるとバックトラックします。
- 線形時間で動作し、多くのグラフアルゴリズムの基盤となっています。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
深さ優先探索 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity