13

私が使用した場合、BFSの時間の複雑さは何だろうと思っていました:

  • 隣接行列
  • 隣接リスト
  • エッジ リスト

それは彼らの空間の複雑さと同じですか？

4

4 に答える 4

19

隣接行列を使用して実装された BFS の複雑さは になりますO(|V|²)。そして、隣接リストによって実装された場合はO(|V| + |E|).

隣接行列の場合、なぜそれが多いのですか?

これは主に、特定の頂点 'U' に隣接するエッジを見つけるたびに、AdjacencyMatrix[U]もちろん長さである配列全体をトラバースする必要があるため|V|です。

BFS がフロンティアとして進んでいると想像してみてください。Sレベル にある開始頂点 を取得します0。に隣接するすべての頂点Sはレベル になります1。次に、レベルを持たないレベル 1 のすべての頂点の隣接するすべての頂点をレベル にマークします2。したがって、すべての頂点は 1 つのフロンティアにのみ属します。これらの各フロンティアは、異なるレベルに対応しています。また、要素がフロンティアにある場合は、隣接する頂点を一度チェックしますが、これにはO(|V|)時間がかかります。フロンティアは|V|アルゴリズムの過程で要素をカバーするため、合計時間は になりO(|V| * |V|)ますO(|V|²)。

Adjacency Lists and Matrix によって実装された場合の BFS の複雑さの違いは、Adjacency Matrix では、どのノードが特定の頂点に隣接しているかを判断するためにO(|V|)、エッジの数に関係なく時間がかかるという事実が原因で発生します。一方、隣接リストでは、エッジはすぐに利用できるため、隣接する頂点の数に比例して時間がかかります。これは、すべての頂点の合計 |V| です。|E|です。したがって、隣接リストによる BFS は O(|V| + |E|) を返します。

于 2015-02-09T18:39:07.923 に答える
5

時間の複雑さは必然的に表現に依存します。

このリンクが示唆するように、隣接リストの時間計算量は O(V + E) であり、隣接行列の場合は O(V 2 ) です。

于 2014-01-28T06:18:10.403 に答える
2

まず、時間の複雑さを見てみましょう。隣接行列を疎行列として格納できる場合、空間の複雑さは同じになります。疎行列は本質的に隣接行列のゼロ以外の値のみを格納するため、隣接リスト表現と同じ空間の複雑さ、つまり O(|V| + |E|) を持ちます。

次に、時間の複雑さです。BFS 検索を行う 1 つの方法は、通常は隣接リスト表現、つまり O(|V| + |E|) を使用するため、スパース隣接行列を単純に使用することです。

隣接行列で BFS を実行する別の方法は、Y=GX を繰り返し適用して疎行列とベクトルの乗算を使用することです。ここで、G は疎隣接行列であり、X はフロンティアに 1 を持つ疎ベクトルです。この操作は基本的に G の列の組み合わせです。各乗算が G の各列でアクセスされるデータのサイズとベクトル X の非ゼロの数に比例する時間がかかるようにこの操作が実装されている場合、時間の複雑さは次のようになります。また、O(|V| + |E|) になります。このアプローチの利点は、X をいくつかの BFS 検索の最前線を表す疎行列に置き換えることで、複数の BFS 検索に簡単に拡張できることです。詳細については、スパース行列を使用したグラフ アルゴリズムの実装に関するこのホワイト ペーパーを参照してください。

頂点の近傍を見つけるにはコストがかかるため、通常、エッジ リストは BFS には使用されません。

于 2016-11-02T15:53:46.820 に答える
0

グラフのさまざまな表現の時間計算量:

1. エッジ リスト:

エッジ リストは、リスト内のすべてのエッジで構成されます。BFS を実行するには、時間の複雑さがO(E^2)です。すべてのエッジについてu->v、エッジ リスト全体をトラバースし、ソース頂点が存在するエッジを見つけてu探索し、次にu->vBFS を実行する頂点 'v' を探索する必要があるためです。

Eエッジの数はどこにありますか。

ソース インデックスと宛先インデックスに基づいてエッジを並べ替えると、並べ替えられたリストは BFS 順になります。リストをトラバースするだけで、BFS を取得できます。

時間計算量はO(E*log(E))、エッジ リストを並べ替えるためのものです。

2.隣接リスト

隣接関係はキーのマップであり、すべての頂点がキーであり、そのキー頂点に付随する、または隣接する頂点のリストを指します。

BFS を実行するには、任意の頂点をキューに入れて訪問済みにし、キュー [0] をポップし、開始頂点を選択し、隣接するすべての頂点を探索し、それらを訪問済みにしてキューに入れ、同様にqueue[0] を呼び出して、キューが空になるまで、アクセスしていないすべての頂点を探索します。すべての頂点について、隣接する未訪問の頂点 (エッジ以外は何もない) のみをトラバースしています。

したがって、時間複雑度はO(V+E)

3.マトリックス

マトリックス表現では、すべての頂点について、すべての頂点をトラバースし、未訪問の頂点があるかどうかを確認する必要があります。すべての頂点について、すべての頂点をトラバースしているため、

時間複雑度はO(V^2)

于 2020-09-13T17:42:27.423 に答える