Code
C++
#include <bits/stdc++.h>
using namespace std;
// Defining number of vertices
#define V 5
/* a utility function that searches the set of vertices not yet included in MST for the vertex with the lowest key value. */
int minKey(int key[], bool mstSet[])
{
// Initializing the min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
/* A useful function to print the builtin MST contained in parent[] */
void printMST(int parent[], int graph[V][V])
{
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << "  " << i << " \t"
<< graph[i][parent[i]] << " \n";
}
/* For a graph represented using adjacency matrix representation, there is a function to construct and print MST. */
void primMST(int graph[V][V])
{
// array that stores MST
int parent[V];
// Key factors utilised to select the cut's minimal weight
int key[V];
// to display a collection of vertices used in MST
bool mstSet[V];
// Set all keys to INFINITE at start.
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
/* Include the initial vertex in MST at all times. To ensure that this vertex is chosen as the initial vertex, set key to 0. */
key[0] = 0;
parent[0] = 1; // In MST first node is always root
// The MST of V vertices
for (int count = 0; count < V  1; count++) {
/* Choose the minimum key vertex from the collection of vertices that aren't yet part of MST. */
int u = minKey(key, mstSet);
// adding picked vertex to MST
mstSet[u] = true;
/* Update the neighbouring vertices' parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST */
for (int v = 0; v < V; v++)
/* Only the nearby vertices of m mst make graph[u][v] non zero. For vertices not yet included in MST, Set[v] is false. Only change the key if graph[u][v] is less than key[v]. */
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// printing the MST
printMST(parent, graph);
}
// main code
int main()
{
int graph[V][V] = { { 0, 1, 0, 0, 3 },
{ 1, 0, 7, 0, 2 },
{ 0, 7, 0, 2, 10 },
{ 0, 0, 2, 0, 5 },
{ 3, 2, 10, 5, 0 } };
// printing the solution
primMST(graph);
return 0;
}
Python3
import sys
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
# A useful function to print the builtin MST contained in parent[]
def printMST(self, parent):
print("Edge \tWeight")
for i in range(1, self.V):
print(parent[i], "", i, "\t", self.graph[i][parent[i]])
""" A useful function that searches the set of vertices not yet included in the shortest path tree for the vertex with the lowest distance value. """
def minKey(self, key, mstSet):
# Initializing the min value
min = sys.maxsize
for v in range(self.V):
if key[v] < min and mstSet[v] == False:
min = key[v]
min_index = v
return min_index
def primMST(self):
key = [sys.maxsize] * self.V
parent = [None] * self.V # array for storing MST
key[0] = 0
mstSet = [False] * self.V
parent[0] = 1 # First node is always the root of MST
for cout in range(self.V):
"""Choose the minimum key vertex from the collection of vertices that aren't yet part of MST."""
u = self.minKey(key, mstSet)
# adding picked vertex to MST
mstSet[u] = True
""" Update the neighbouring vertices' parent index and key value for the selected vertex. Only take into account vertices that have not yet been added to MST"""
for v in range(self.V):
if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
self.printMST(parent)
# Driver's code
if __name__ == '__main__':
g = Graph(5)
g.graph = [[ 0, 1, 0, 0, 3 ],
[ 1, 0, 7, 0, 2 ],
[ 0, 7, 0, 2, 10 ],
[ 0, 0, 2, 0, 5 ],
[ 3, 2, 10, 5, 0 ] ]
g.primMST()
Output
Edge Weight
0  1 1
3  2 2
4  3 5
1  4 2
Complexity
Time Complexity O(V^{2}): The time complexity of Prim's algorithm can be decreased to O(E log V) with the use of a binary heap if the input graph is represented using an adjacency list. In this implementation, the spanning tree is always believed to begin at the graph's root.
Space Complexity: O(V)
Check out this problem  No of Spanning Trees in a Graph
Frequently Asked Questions
What are a tree and a spanning tree?
One sort of graph is a tree. A subgraph of the graph that is a tree and spans every vertex is called a spanning tree.
What are the properties of a spanning tree?
There is exactly the same number of edges and vertices in each of a graph's potential spanning trees. A cycle can never be found inside a spanning tree. If we remove one edge from the spanning tree, it will become unconnected since spanning trees are always minimally linked.
Why Prim's algorithm is greedy?
Input is rearranged by Prim's Algorithm in order to select the least expensive edge. In the sense that the algorithm strives to readjust the input to its own convenience at each iteration, we refer to Prim's Algorithm as an adaptive greedy algorithm.
Why is Prims better than Kruskal?
Prim's algorithm has an advantage over Kruskal's in that it is more complex. Prim's approach is therefore useful for handling dense networks with a large number of edges. However, when numerous edges with the same weight occur, Prim's approach doesn't provide us much control over the selected edges.
Which is faster Prim or Kruskal?
The Prim algorithm returns connected components and solely utilizes connected graphs. In dense graphs, Prim's method operates more quickly. In sparse graphs, Kruskal's algorithm operates more quickly.
Conclusion
In the above article, we have discussed the following topics:

Spanning Tree

Finding spanning tree using Prim’s algorithm

Example of Prim’s algorithm

Implementation of Prim’s algorithm
If you want to learn more, check out our articles on Construct the Full Kary Tree from its Preorder Traversal, Regular and Bipartite graphs, and Planar and NonPlanar Graphs.
Happy Coding!