Scribd
Upload
3 views18 pages

Lecture - Prim's Algorithm

Prim's algorithm is a greedy algorithm used to find a minimum spanning tree for a weighted undirected graph by connecting vertices with the least weight edges without forming cycles. Developed by Vojtěch Jarník in 1930, it operates by selecting edges iteratively until the tree is complete. The algorithm has applications in network design, cycle creation, and electrical wiring, with a time complexity of O((V+E)logV).

Uploaded by

juttsufyan318
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views18 pages

Lecture - Prim's Algorithm

Prim's algorithm is a greedy algorithm used to find a minimum spanning tree for a weighted undirected graph by connecting vertices with the least weight edges without forming cycles. Developed by Vojtěch Jarník in 1930, it operates by selecting edges iteratively until the tree is complete. The algorithm has applications in network design, cycle creation, and electrical wiring, with a time complexity of O((V+E)logV).

Uploaded by

juttsufyan318
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Analysis of Algorithms

Analysis of algorithm by Abid Farooq


Prim’s Minimum spanning tree
• In computer science, Prim's algorithm is a greedy
algorithm that finds a minimum spanning tree for
a weighted undirected graph. This means it finds a subset of
the edges that forms a tree that includes every vertex, where
the total weight of all the edges in the tree is minimized. The
algorithm operates by building this tree one vertex at a time,
from an arbitrary starting vertex, at each step adding the
cheapest possible connection from the tree to another vertex.
• The algorithm was developed in 1930
by Czech mathematician Vojtěch Jarník.
• Prim’s algorithm helps to find the minimum spanning tree from
a graph. It determines the subset of edges that include every
vertex of the graph. It also reduces the sums of the weights of
the edges. Also, this algorithm begins with the root node and
checks all the adjacent nodes including all the connecting
edges at each step. Moreover, it selects the edges with fewer
weights that cause no cycles.
Working of Prim’s algorithm:
Prim's algorithm starts with the single node and explores all the
adjacent nodes with all the connecting edges at every step. The
edges with the minimal weights causing no cycles in the graph
got selected.
Step 1 – Select a starting vertex or a root vertex
Step 2 – Repeat step 3 and 4 until there are fringe vertices
Step 3 – Select an edge connecting the tree vertex and fringe
vertex that has a minimum weight
Step 4 – Add the selected edge and the vertex to the minimum
spanning [Link] step 2 until the minimum spanning tree is
formed.
Applications:

The applications of prim’s algorithm are –

[Link]’s algorithm can be used in network designing.


[Link] can be used to make network cycles.
[Link] can also be used to lay down electrical wiring
cables.
Algorithm:
Algorithm
Step 1: Select a starting vertex
Step 2: Repeat Steps 3 and 4 until there are fringe vertices
Step 3: Select an edge ‘e’ connecting the tree vertex and
fringe vertex that has minimum weight
Step 4: Add the selected edge and the vertex to the
minimum spanning tree T
[END OF LOOP]
Step 5: EXIT
Time Complexity:
The time complexity of the Prim’s Algorithm is O((V+E
)logV)because each vertex is inserted in the priority queue
only once and insertion in priority queue take logarithmic
time.

You might also like