Prim's Algorithm is a greedy algorithm that finds a minimum spanning tree for weighted undirected graphs. Spanning Trees: Retain a minimal set of edges so that graphs remain connected. A tree is a minimally connected graph. Adding an edge to a tree creates a loop and removing an edge disconnects the graph. In this graph, the red edges form a Spanning tree Minimum Cost Spanning Tree: Add the cost of all the edges in the Tree Amount different spanning trees, choose the one with a minimum one Finding Minimum Cost Spanning Trees using Prim's Algorithm Strategy: Incrementally grow the minimum cost spanning tree Start with the smallest weight edge overall Extend the current tree by adding the smallest edge from the vertex of the tree to a vertex not yet reached For example, consider: Start with the smallest edge which is between Vertex 1 and Vertex 3 in the above given example. After this, we can extend the tree by choosing edges that are connected with Vertex 1 and Vertex 3. This ...
Hey! Thanks for landing on my blog! I am Zeaan Pithawala, an undergraduate student in India. I am pursuing B.Sc. (Hons.) Biochemistry from Sri Venkateswara College, University of Delhi. I have been coding since a very early age but at the same time, I was intrigued by Science too. I want to leverage the computational power accessible nowadays and combine it with biochemistry to tackle some of the biggest challenges in modern biology.