1

私は C で Prim MST を使用しており、関数は隣接行列を取ります。もちろんの重みを考えるとA[i][j]。

これまでに見つけた最小エッジを追跡する先行配列があるとします。 predecessor[u]=v{これも最後の MST です}

ここで、現在の行列を変更し、重みを 1 に変更したいと考えていA[i][j]ます。これは、先行配列にもエッジ (インデックス) が存在していたときです。それ以外の場合は、ゼロに変更します。

どうすればいいですか？これが私の解決策です：

for (x....)
   for (y...)
      if (x!=y && (p[x]==y || p[y]==x))
         set to 1
      else
         set to 0
4

1 に答える 1

2

あなたの疑似コードは正しいです。これにより、プリムのアルゴリズムによって見つかったツリーを表す 0-1 行列が得られます。ただし、この保存方法は O(n^2) のスペースを必要とするため、かなりコストがかかりますが、ツリーは O(n) メモリに保存できます。

または、行列を O(n^2) でゼロに初期化してから、O(n) 時間でエッジを追加できます。

 for (x ...)
    for (y ...)
       A[x][y] = 0

 for (x ...)
    if (p[x] != x)
      A[x][p[x]] = A[p[x]][x] = 1
于 2012-07-24T19:26:04.493 に答える