Prim算法的分析

Question

任何人都可以解釋爲什麼我們使用PRIM算法中使用密鑰數組（即key []） 的重要性，它處理最小生成樹問題。

PRIM_MST(G,W,R)//G->graph,W->weighted matrix,R->root vertex 
------------------------- 

for v<-v[G] 
    key[v]<-infinity 
    pred[v]<-NIL  //pred[]-->predecessor array 
key[v]=0 
Q<-v[G]    //Q-->priority queue 
while Q!=NULL 
    u<-EXTRACT_MIN(Q) 
     for v<-adj[u] //adj[]--> adjacency list matrix 
      if v belongs to Q && w(Q,v)<key[v] 
       pred[v]<-u,key[v]<-w(u,v) 

Answer 1

Key是基本上在該MST

對算法期間上的頂點到達的施工過程中導致了圖中的特定頂點的邊的值，它檢查最小加權邊緣連接集合A（已經遍歷的頂點集合）和集合B（邊緣集合尚未遍歷）。它遵循這個最小邊，並將新到達的頂點（在該最小邊之後到達的頂點）的關鍵點作爲該最小邊的權重