[解決済み] 深さ優先グラフアルゴリズムの時間複雑性【非公開

質問

私は時間の複雑さを学び始めていて、いくつかの簡単なソートの時間の複雑さを例題で調べました。

を持つグラフの深さ優先探索の平均的な時間複雑性をどのように計算するのか知りたかったのです。 |V|=n と |E|=m 開始ノードを「u」、終了ノードを「v」とする。

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

DFSの時間計算量はO(n + m)である。これは、各ノードを一度だけ訪問することと、木の場合（サイクルがない）、すべての辺を一度だけ交差するという事実を考慮して得られた複雑さです。

例えば、開始ノードをu、終了ノードをvとした場合、vが最後に訪れたノードとなる最悪のケースを考えます。 そこで、uの最初の隣接連結成分、2番目の隣接連結成分、そして最後の隣接連結成分まで訪問し、vを見つけることになるのです。