graph-algorithm - Prim算法分析

Question

谁能解释我们为什么使用或在处理最小生成树问题的PRIM'S ALGORITHM 中使用键数组（即键[]）的重要性。

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（尚未遍历的边集合）的最小加权边。它跟随这个最小边，并将新到达的顶点的键（跟随这个最小边之后到达的那个）作为这个最小边的权重