完全なグラフの幅優先探索の複雑さは何ですか？

BFSの複雑さは、線形すなわちO（V + E）であると言われているが、有向完全グラフのエッジの総数は、V *（V-1）グラフ。だから、BFSはO（V^2）時間をかけて完全なグラフをたどるでしょうか？完全なグラフの幅優先探索の複雑さは何ですか？

出典

2017-08-25 Uttakarsh Tikku

答えを確認してください。不便をおかけして申し訳ありません。私は腹がBFSであることを見なかった。私の答えをチェックしてください。 – coderredoc

はい、私はすでに数学を行ったと仮定します。

O(V+E) = O(V + V*(V-1)) 
     = O(V + V*V - V) 
     = O(V*V)

出典

2017-08-25 02:50:31

この結果から、隣接リストを使用するBFSの最悪のケースは線形ではなく二次式であると結論付けることができますか？ –

@UttakarshTikkuアルゴリズムの入力の大きさは線形で、頂点の数は2次です。 –

ありがとう！これは大きな助けとなりました！ –

BFSはO(V + E)時間で実行され、グラフは隣接リスト構造で表されます。

密集したケースでも、答えはO(V+E)になります。（表現は隣接リストです）。

隣接行列の場合O(V^2)。

グラフがどのようなものであっても、常に最初に開始点のネイバーをカバーします。それから隣人のためにこれを繰り返してください。だから、それは常にO(V+E)時にトラバースする必要があることがわかりますが、それは隣接行列のために難しい表現です。したがって、O(V^2) になります。私たちが望むすべての時間が与えられた頂点に隣接するエッジが何であるかを見つけるために、これはある

_{「U」を、私たちは長さである配列全体adjmatrix[u]を、トラバース| V |}

出典

2017-08-25 02:41:33 coderredoc

私がここで得ているのは、頂点の数とここでの辺の数の関係です。完全なグラフの辺の数は、完全な有向グラフの場合、頂点の数、正確にはV *（V-1）の関数です。 –

はい、表現は重要です。それは私が言ったことです。 – coderredoc

完全なグラフの幅優先探索の複雑さは何ですか？

答えて

関連する問題