This question asks about Prim\'s algorithm which is used to find the minimun spa

Question

This question asks about Prim's algorithm which is used to find the minimun spanning tree of a graph.

a) What is the problem that Prim's algorithm is trying to solve? What is the end output of the algorithm? Is this output a precise/best solution or is it only an approximation?

b) In broad terms, how does the algorithm work? (No code needed in the explanation). Be as thorough as possible in your explanation.

c) Using the description you gave from b), what is the runtime complexity of Prim's algorithm and why.

Explanation / Answer

A) Prim's Algorithum is also knows as Greedy algorithm because it used the greedy approach which is used to find minimum spanning tree for a weighted undirected graph.

Prim's algorithm is used to find the minimum cost of a tree. Sum of the weight of all the edges in the tree is known as the cost of a tree. It selects the edge with smallest weight .

End output : used to find minimum spanning tree for a weighted undirected graph.

It is one of the best algorithm because running time got decreased in this.

b)

Algorithm working :

The working of prim's algorithm is very simple. Select any vertex in the tree. Then select the cheapest vertex from the selected vertex and go so on but make sure there is no cycle is present in the tree. When all the vertex got selected our algorithm is complete.

C) Compexity : O((V+E)logV)

the runtime complexity is very less because each vertex is inserted only once in the queue and logarithmic time is taken to insert the in the queue.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.