algorithm - 深さ優先グラフアルゴリズムの時間計算量

Question

私は時間計算量を学び始めており、いくつかの単純なソートの時間計算量の例を調べました。

グラフで深さ優先探索の平均時間計算量を計算する方法を知りたいと思いました。開始ノードを「u」、終了ノードを「v」とします|V|=n。|E|=m

Answer 1

DFSの時間計算量はO（n + m）です。各ノードに1回だけアクセスし、ツリー（サイクルなし）の場合はすべてのエッジを1回通過するという事実を考慮すると、この複雑さが生じます。

たとえば、開始ノードがuで、終了ノードがvの場合、vが最後にアクセスされるノードになるという最悪のシナリオを考えています。したがって、u連結成分の最初の近傍、次に2番目の近傍の連結成分、というように、最後の近傍の連結成分にアクセスし始めます。ここでvが見つかります。各ノードに一度だけアクセスし、交差しませんでした。同じエッジを複数回。

Answer 2

グラフが隣接リストの形式で与えられている場合はO（n + m）になりますが、グラフが隣接行列の形式である場合は、全体をトラバースする必要があるため、複雑さはO（n * n）になります。エッジが見つかるまで行。