Need help in understanding Prims algorithm specifically each

Need help in understanding Prim\'s algorithm, specifically each line in the algorithm. I realize several calls to other algorithms are made. Also need help in seeing how it is traced, I have pictures below., could you also say how the running time is calculated? Thanks,

Prim s Algorithm Start with one vertex Part of inputs, as it could be any vertex Repetitively add an edge with minimum weight to existing tree without forming a cycle until done Tree grows one vertex at a time Stop when all vertices are connected That is, stop when the number of edges included is IVM 1

Solution

Prim\'s algorithm is mainly the greedy algoritm which is finding the minimum spanning tree for a conneced weighted undirected graph which has no cycles.

Now i will explain each line in this algorithm

1. Prim(G,w,r)

2. Here Q=0 means this is the start to all the edges in the minimum spanning tree . so in begining it is empty

3. for each vertex(u) in the graph G. ( Each vertex in the graph has two attributes key and parent)

4. each key is initialize to infinity

5. each parent is initialize to null

6. now we will insert a vertex to the empty tree Q

7. now we will take that vertex as the root so now we consider its key as 0. here Q contains all the vertices in the graph.

8. by taking the while loop

9. find the vertex which is having minimum key value of all the vertices in the graph

10. of all the adjacent vertices to the taken vertex

11. taking a for loop to find the vertex which is having minimum key

12.and make our vertex as the parent to that vertex of minimum key vertex.

13. and we will move to that child vertex from the parent vertex

14. until we travel to all the vertices

finally we will return the Q

Running time:-

Starting from the root vertex calculate the total weight(key) of the vertices which we travel in the graph with minimum weight.

For the given example we take a as the root vertex and it is having two vertices adjacent to it among these two b has minimum key of 4.

we travels to a--->b like this we also travels from b--->c

c is having three adjacent vertices i, d, f among all these i having minimum key so we will travel to i

if we go to i vertex we do not travel to all the vertices with minimum weight(key).next we still be there in c and choose one from remaining two vertices so we will go to f vertex

from \'f\' vertex to to \'g\' which having weight minimum . from \'g\' to go to \'h\'

we remember that from the root vertex we can travel to all the vertices.

so from c vertex to we will go to d and then go to \'e\' vertex