2

O( V + E )最悪の場合、すべての頂点とすべてのエッジが探索されるため、グラフ トラバーサルでの BFS の時間の複雑さは理解しています。

さて、正確な時間は複雑ですv+2Eか??

すべての頂点が 1 回探索されます+ すべての隣接する頂点

のすべての頂点の次数の合計graph= No of edges*2= 2E

したがって、時間の複雑さはn+2E..私は正しいですか?

4

2 に答える 2

0

仮定

G が接続され、無向であると仮定しましょう。接続されていない場合は、以下のアイデアを G のすべての接続コンポーネントに個別に適用できます。さらに、G が隣接リストとして表され、すべての頂点 v について、たとえばルックアップ テーブルを使用して、v が O(1) 時間で訪問されたかどうかを判断できると仮定しましょう。

分析する

BFS の正確なステップ数をカウントしたい場合は、次のことを確認できます。

  1. G は接続されているため、BFS はすべての頂点を 1 回だけ訪問するため、|V| をカウントします。ノードでの訪問。1 回の訪問で、訪問した現在の頂点をマークするだけでなく、エッジのループを数えないで、より多くの操作を実行できることに注意してください。

  2. カウントしたい頂点 v ごとに、BFS がこの頂点で検査するエッジの数。

BFS を実行するには、v のすべてのエッジをループする必要があります。1 つのエッジをスキップすると、BFS が正しくないことを簡単に示すことができます。したがって、すべてのエッジが 2 回検査されます。

ここで1つの疑問が生じるかもしれません。頂点 v のエッジ (p, v) を調べる必要があるかどうかを尋ねる人がいるかもしれません。ここで、p は、既に構築された BFS ツリーの v の親です。つまり、p から直接 v にたどり着きました。もちろん、このエッジを考慮する必要はありませんが、このエッジをスキップすることを決定すると、少なくとも 1 つの追加操作が必要になります。

for (v, u) in v.edges:
    if u == p: # p is the parent of v in already constructed tree
        continue
    if not visited[u]:
        BFS(u, parent=v)

以下のコードと同じ数のエッジを調べますが、1 つを除くすべてのエッジに対して、1 つではなく 2 つの if ステートメントを実行するため、より複雑になります。

for (v, u) in v.edges:
    if not visited[u]: # if p is the parent of v, then p is already visited
        BFS(u, parent=v)

結論

エッジ (v, p) をスキップする別の方法を開発することもできますが、常に少なくとも 1 つの操作が必要になるため、無駄な労力になります。

于 2013-09-05T00:29:01.583 に答える