Prim's Algorithm
The graph is a set of vertices connected with the help of edges. A graph may be directed or undirected, and all the vertices are connected in the graph. We can represent a graph using an array of vertices and a two-dimensional array for edges. We can perform basic operations on graphs: adding a vertex, displaying vertex, adding edges, etc.
Prim’s Algorithm
Prim's algorithm is a greedy algorithm, which finds a minimum spanning tree for weighted undirected graphs. It finds the subset of edges that includes every vertex, and prim's algorithm starts with an empty spanning tree.
Prim’s algorithm starts with an empty spanning tre
Algorithm
- Create a minimum spanning tree set that will keep track of vertices included in MST.
- Give a key value to every vertex in the input graph. Assign 0 to the first vertex, which will make it easy to pick.
- While a set of minimum spanning tree doesn't contain all vertices
- Pick the vertex which has the minimum key value.
- Insert the element in that MST set.
- Update the key value of the inserted element with all other adjacent elements.
Advantages of Prim’s algorithm
- Prim's algorithm is suitable for graphs containing more edges.
- The tree which is growing always stays connected.
- It is faster for dense graphs.
