168

BFSの基本的なアルゴリズム：

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

したがって、時間計算量は次のようになると思います。 

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

v頂点は1どこですかn

まず、私が言ったことは正しいですか？第二に、これはどうですかO(N + E)、そしてなぜ本当に素晴らしいのかについての直感。ありがとう

4

9 に答える 9

313

あなたの合計

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

次のように書き直すことができます

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

最初のグループはO(N)で、もう一方のグループはですO(E)。

于 2012-07-13T10:29:30.750 に答える
44

DFS（分析）：

  • 頂点/エッジラベルの設定/取得には時間がかかりO(1)ます
  • 各頂点には2回ラベルが付けられます
    • かつては未開拓だった
    • 一度訪問した
  • 各エッジには2回ラベルが付けられます
    • かつては未開拓だった
    • DISCOVERYまたはBACKとして1回
  • メソッドincidentEdgesは、頂点ごとに1回呼び出されます
  • O(n + m)グラフが隣接リスト構造で表されている場合、DFSは時間内に実行されます
  • それを思い出しますΣv deg(v) = 2m

BFS（分析）：

  • 頂点/エッジラベルの設定/取得にはO（1）時間がかかります
  • 各頂点には2回ラベルが付けられます
    • かつては未開拓だった
    • 一度訪問した
  • 各エッジには2回ラベルが付けられます
    • かつては未開拓だった
    • DISCOVERYまたはCROSSとして一度
  • 各頂点はシーケンスに1回挿入されますLi
  • メソッドincidentEdgesは、頂点ごとに1回呼び出されます
  • O(n + m)グラフが隣接リスト構造で表されている場合、BFSは時間内に実行されます
  • それを思い出しますΣv deg(v) = 2m
于 2012-07-13T10:28:47.380 に答える
29

あまり形式的ではなく非常に単純化されています。すべてのエッジは正確に2回考慮され、すべてのノードは正確に1回処理されるため、複雑さは頂点の数だけでなくエッジの数の定数倍でなければなりません。

于 2014-12-17T06:04:35.303 に答える
18

これに対する直感的な説明は、単一のループを分析するだけです。

  1. 頂点にアクセス->O（1）
  2. すべての入射エッジでのforループ->O（e）ここで、eは特定の頂点vに入射するエッジの数です。

したがって、単一ループの合計時間はO（1）+ O（e）です。次に、各頂点が1回訪問されるので、各頂点について合計します。これは与える

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)
于 2017-08-07T09:27:56.877 に答える
14

時間計算量がn^2 + 2n + 7の場合、O（n ^ 2）と記述されるため、 時間計算量はO(E+V)代わりになります。O(2E+V)

したがって、O（2E + V）はO（E + V）と表記されます。

n ^ 2とnの違いは重要ですが、nと2nの違いは重要ではないからです。

于 2015-09-10T15:39:03.750 に答える
5

すべてのエッジが2回考慮され、すべてのノードが1回訪問されたと思うので、合計時間計算量はO（2E + V）である必要があります。

于 2015-07-21T08:23:36.493 に答える
3

短くて簡単な説明：

最悪の場合、すべての頂点とエッジにアクセスする必要があるため、最悪の場合の時間計算量はO（V + E）です。

于 2016-07-27T04:17:21.767 に答える
0

Bfsでは、隣接する各頂点が1回キューに挿入されます。これは、頂点のエッジを調べることによって行われます。訪問した各頂点はマークされているため、再度訪問することはできません。各頂点は1回だけ訪問され、各頂点のすべてのエッジがチェックされます。したがって、BFSの複雑さはV+Eです。DFSでは、各ノードはすべての隣接エッジのリストを維持します。次に、各ノードについて、線形時間に1回だけ隣接リストをトラバースすることにより、すべての隣接ノードを検出する必要があります。有向グラフの場合、すべてのノードの隣接リストのサイズの合計はE（エッジの総数）です。したがって、DFSの複雑さはO（V + E）です。

于 2021-11-30T16:39:47.367 に答える
-1

これはO（V + E）です。これは、Vのvにアクセスするたびに、Eの各eにアクセスする必要があるためです。ここで| e | <=V-1。VのvへのV訪問があるので、それはO（V）です。ここで、V * |e|を追加する必要があります = E => O（E）。したがって、合計時間計算量はO（V + E）です。

于 2020-09-26T06:53:32.817 に答える