Prim’s Algorithm

Overview

Prim’s Algorithm is a fundamental graph algorithm in computer science, used to determine the minimal spanning tree for a connected weighted graph.
It starts from an arbitrary node (vertex), then successively adds the nearest node to the growing network.

A graph is a set of vertices (or nodes) connected by lines, called edges.
A weighted graph is a graph with a numerical value, or weight, associated with each edge.
A spanning tree of a graph is a tree composed of all the vertices of the graph and some of the edges.
A minimum spanning tree is a spanning tree with the smallest possible total edge weight.
Prim’s Algorithm efficiently finds the minimum spanning tree of a weighted graph, which is useful in situations where the least costly solution is required.

Start with an arbitrary node and mark it as part of the growing network, also known as the tree.
Find the edge with the smallest weight that connects a node in the tree with a node not in the tree. Add that edge and the new node to the tree.
Repeat the previous step until all nodes are in the tree.

After starting with the initial node, Prim’s Algorithm focuses on edges, considering the smallest weight edge that connects the growing tree to a new vertex.
Unlike Dijkstra’s Algorithm, which looks at the total edge weight of paths, Prim’s Algorithm only compares the weights of individual edges when deciding which edge to add next to the tree.

Routing in computer networks: Prim’s algorithm minimises the total length of the routes, which reduces overall network cost.
Circuit design: Physical wires in a circuit introduce a delay based on their length, this algorithm minimises total wire length, reducing the circuit delay.

Prim’s Algorithm doesn’t work if the graph is not connected i.e., if there’s any vertex that can’t be reached from the others.

Kruskal’s Algorithm is another method to solve the minimum spanning tree problem, but it adds edges in order of weight without regard to proximity to the growing network.
Dijkstra’s Algorithm is also a graph search algorithm, but it determines the shortest path from one node to all other nodes in the graph, instead of finding the minimum spanning tree.