Prim's Algorithm is a method used in graph theory to find the Minimum Spanning Tree (MST) of a weighted, undirected graph. It starts from a random vertex and keeps adding the smallest possible edge to build the MST step by step.
prim(v): pq = new PriorityQueue() mark v as visited pq.insert(v.outgoingEdges) while (!pq.isEmpty()): c = pq.removeMin() if (c.endNode is unvisited): mark c.endNode as visited add c to tree pq.insert(c.endNode.outgoingEdges to unvisited nodes)
The following diagram shows how Prim's Algorithm builds the MST step by step:
If you'd like to learn more about Prim's Algorithm, check out the link below:
Wikipedia: Prim's AlgorithmKruskal's Algorithm is another way to find the MST of a graph. Unlike Prim's, which starts with a vertex, Kruskal's Algorithm sorts all the edges by weight and adds them one by one, making sure no cycles are created. It keeps adding edges until all vertices are connected.