Scribd
Upload
23 views8 pages

Prim's Algorithm

Prim's Algorithm is a greedy algorithm that constructs a minimum spanning tree for a weighted, connected, undirected graph by iteratively adding the smallest edge that connects a vertex in the tree to a vertex outside of it. The process continues until all vertices are included, ensuring no cycles are formed. It is commonly used in network design and transportation planning.

Uploaded by

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

Prim's Algorithm

Prim's Algorithm is a greedy algorithm that constructs a minimum spanning tree for a weighted, connected, undirected graph by iteratively adding the smallest edge that connects a vertex in the tree to a vertex outside of it. The process continues until all vertices are included, ensuring no cycles are formed. It is commonly used in network design and transportation planning.

Uploaded by

Ms. Pavithra D
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 8

PRIM’S ALGORITHM

Prim’s Algorithm
• It is a greedy algorithm that finds a minimum
spanning tree for a weighted connected and
undirected graph.
Steps:
Step 1: (Consider all the vertices first)
Start with any vertex of the graph.

Step 2:Select an adjacent edge with minimum weight


and add that edge to the graph if it is not
forming any cycle.
if cycle forms then discarded.

Step 3:Repeat step2 till all vertices are covered.


Example:

25
A BB
14
10
12

C
C F G
22
17

23 11
D 20 E
Example:

7
A B 11
E

4 9
3

C D
10
ALGORITHM:

VT ← {v0}
ET ← ∅
for i ← 1 to |V | − 1 do
find a minimum-weight edge e∗ = (v∗, u∗) among all
the edges (v, u)
such that v is in VT and u is in V − VT
VT ← VT ∪ {u∗}
ET ← ET ∪ {e∗}
return ET
APPLICATION:

• Network design (e.g., designing road networks,


telecommunication networks, or laying cables for
internet or TV).
• Transportation planning.
TRY IT YOURSELF:

You might also like