3

プリム法を使用してMSTを解決するコードを作成しました。この種の実装（優先キューを使用）はO（E + VlogV）= O（VlogV）である必要があることを読みました。ここで、Eはエッジの数、Vはエッジの数ですが、コードを見ると単純に見えません。誰かが私のためにこれを片付けることができれば私はそれをいただければ幸いです。

私には、実行時間はこれであるように思われます：

whileループにはO（E）回かかります（すべてのエッジを通過するまで）そのループ内で、O（logE）時間かかるQから要素を抽出します。そして、2番目の内側のループにはO（V）時間がかかります（すべての頂点を追加する必要があるため、このループがV回実行されることは明らかですが、毎回このループを実行するわけではありません）

私の結論は、実行時間は次のとおりです。O（E（logE + V））= O（E * V）。

これは私のコードです：

#define p_int pair < int, int >

int N, M; //N - nmb of vertices, M - nmb of edges
int graph[100][100] = { 0 }; //adj. matrix
bool in_tree[100] = { false }; //if a node if in the mst
priority_queue< p_int, vector < p_int >, greater < p_int > > Q; 
/*
keeps track of what is the smallest edge connecting a node in the mst tree and
a node outside the tree. First part of pair is the weight of the edge and the 
second is the node. We dont remember the parent node beaceuse we dont need it :-)
*/

int mst_prim()
{
 Q.push( make_pair( 0, 0 ) );

 int nconnected = 0;
 int mst_cost = 0;
 while( nconnected < N )
 {
      p_int node = Q.top(); Q.pop();

      if( in_tree[ node.second ] == false )
      {
           mst_cost += node.first;
           in_tree[ node.second ] = true;

           for( int i = 0; i < N; ++i )
                if( graph[ node.second ][i] > 0 && in_tree[i]== false )
                     Q.push( make_pair( graph[ node.second ][i], i ) );

           nconnected++;
      }
 }

 return mst_cost;
}
4

2 に答える 2

2

隣接リストを使用してソリューションを高速化できますが (ただし、密なグラフには使用できません)、それでも、フィボナッチ ヒープなしでは O(V log V) を取得することはできません..

おそらく、Kruskal アルゴリズムの方が理解しやすいでしょう。プライオリティ キューがなく、エッジの配列を 1 回ソートするだけで済みます。基本的には次のようになります。

  • すべてのエッジを配列に挿入し、重みで並べ替えます
  • ソートされたエッジを繰り返し処理し、ノード i と j を接続するエッジごとに、i と j が接続されているかどうかを確認します。そうである場合はエッジをスキップし、そうでない場合はエッジを MST に追加します。

唯一の問題は、2 つのノードが接続されているかどうかをすばやく判断できるようにすることです。これには、次のような Union-Find データ構造を使用します。

int T[MAX_#_OF_NODES]

int getParent(int a)
{
  if (T[a]==-1)return a;
  return T[a]=getParent(T[a]);
}
void Unite(int a,int b)
{
  if (rand()&1)
     T[a]=b;
  else
     T[b]=a;
}

最初に、T をすべて -1 に初期化してから、ノード A と B が接続されているかどうかを確認するたびに、それらの親を比較します - それらが同じ場合、それらは接続されています (このようにgetParent(A)==getParent(B))。エッジを MST に挿入するときは、Union-Find を で更新してUnite(getParent(A),getParent(B))ください。

分析は単純です。エッジをソートし、O(1) を取る UF を使用して反復します。したがって、O(E logE + E ) は O(E log E) に等しくなります。

それだ ;-）

于 2010-01-09T14:44:48.107 に答える
1

以前はアルゴリズムを扱う必要はありませんでしたが、実装したものはWikipediaで説明されているアルゴリズムと一致しません。そこでのアルゴリズムは次のように機能します。

  1. しかし、キューへのすべての頂点。O(V)
  2. キューが空でない間... O(V)
    1. キューから最小の重みでエッジを取得します。O(ログ(V))
    2. 隣接する頂点の重みを更新します。O(E / V)、これは隣接する頂点の平均数です。
    3. キュー構造を再確立します。O(ログ(V))

これは与える

        O(V) + O(V) * (O(log(V)) + O(V/E))
      = O(V) + O(V) * O(log(V)) + O(V) * O(E / V)
      = O(V) + O(V * log(V)) + O(E)
      = O(V * log(V)) + O(E)

まさに期待通り。

于 2009-11-19T17:20:37.800 に答える