0

最小スパニングツリーのプリムアルゴリズムに関するこのMITビデオでは、教授がπ[v] ←u71:16秒に説明しています。しかし、なぜこのステップが必要なのかわかりません。この表記 π[v] ←uは実際にはどういう意味ですか？また、次のアルゴリズムの最後の行はどういう意味ですか？ソースで提供されているアルゴリズム全体は次のとおりです。

Q←V
key[v] ←∞for all v∈V
key[s] ←0for some arbitrary s∈V
while Q≠∅
 do u←EXTRACT-MIN(Q)
   foreach v∈Adj[u]
    do ifv∈Qand w(u, v) < key[v]
      then key[v] ←w(u, v)⊳DECREASE-KEY
           π[v] ←u

At the end, {(v, π[v])}forms the MST
4

1 に答える 1

2

π古い配列変数です。したがって、このコード行は他の割り当てと実際には違いはありません。

ただし、アルゴリズムで行うことは、現在のノードの先行ノードを保存することです。は、任意のノードに対して、（アルゴリズムが完了した後）そのノードの先行関数を提供するため、先行関数πと呼ばれることもあります。nπ[n]

したがってπ、プリムのアルゴリズムによって検出されたパス（=スパニングツリーのエッジ）を再構築するために使用できます。

于 2012-10-01T15:25:20.680 に答える