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

键基本上是在构建MST期间导致图中特定顶点的边上的值

在算法过程中到达顶点时，它会检查连接集合A(已遍历的顶点集合)和集合B(尚未遍历的边的集合)的最小加权边。它跟随这个最小边，并将新到达的顶点(跟随这个最小边之后到达的顶点)的关键点作为这个最小边的权重。