[解決済み] 幅優先と深さ優先の木探索の時間的・空間的複雑性は？

質問

これらのトラバーサルメソッドの時間と空間の複雑さをどのように計算するのか、誰か例を挙げて説明してください。

また、深さ優先の探索に対する再帰的な解法は、時間と空間の複雑さにどのような影響を与えるのでしょうか？

どのように解決するのですか？

BFSです。

時間の複雑さは O(|V|) であり、ここで |V| はノードの数である。すべてのノードをトラバースする必要があります。

空間の複雑さは O(|V|) というのも、最悪の場合、キュー内のすべての頂点を保持する必要があるためです。

DFSです。

時間の複雑さは再び O(|V|) であり、すべてのノードをトラバースする必要があります。

空間の複雑さ - 実装に依存し、再帰的な実装では O(h) 空間の複雑さ [最悪の場合]、ここで h は木の最大深度です。

スタックを使った反復解法は、実はBFSと同じで、キューの代わりにスタックを使っているだけなので、両方が得られます。 O(|V|) 時間および空間の複雑さを得ることができます。

(*) 木の場合、空間的複雑性と時間的複雑性は一般的なグラフの場合とは少し異なることに注意してください。 visited のセットを維持する必要がなく、また |E| = O(|V|) は、だから |E| の要素は実際には冗長です。