Analysis of Prim's Algorithm -

can explain why use or what's importance of using key array(i.e key[]) in prim's algorithm deals minimum spanning tree problem.

prim_mst(g,w,r)//g->graph,w->weighted matrix,r->root vertex -------------------------  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)       v<-adj[u]   //adj[]--> adjacency list matrix            if v belongs q && w(q,v)<key[v]                  pred[v]<-u,key[v]<-w(u,v) 

key value on edge led particular vertex in graph during construction of mst

on arriving on vertex during algorithm, checks minimum weighted edge connecting set a(the set of vertices traversed) , set b(the set of edges not yet traversed). follows minimum edge , puts key of newly arrived vertex(the 1 reached after following min edge) weight of minimum edge