[go: up one dir, main page]
Scribd
Upload
9 views5 pages

Prims

Prim's algorithm is a greedy method used to find the minimum spanning tree of a connected, undirected graph by minimizing the total edge weight. The algorithm involves initializing a starting vertex, updating a priority queue with edges, selecting the minimum edge, and repeating the process until all vertices are included in the tree. An example illustrates the steps of the algorithm, culminating in a minimum spanning tree with a total cost of 10 units.

Uploaded by

omraval0808
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
9 views5 pages

Prims

Prim's algorithm is a greedy method used to find the minimum spanning tree of a connected, undirected graph by minimizing the total edge weight. The algorithm involves initializing a starting vertex, updating a priority queue with edges, selecting the minimum edge, and repeating the process until all vertices are included in the tree. An example illustrates the steps of the algorithm, culminating in a minimum spanning tree with a total cost of 10 units.

Uploaded by

omraval0808
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
You are on page 1/ 5

NAME:RAVAL OM PRAGNESHBHAI

ENROLLMENT NUMBER:220280152057
TOPIC:IMPLEMENTATION OF PRIMS ALGORITHM

WHAT IS PRIMS ALGORITHM?


-Prim's algorithm is a greedy algorithm that finds the minimum spanning tree of a connected, undirected
graph. A minimum spanning tree is a subset of the edges of the graph that forms a tree, connecting all
the vertices and minimizing the total edge weight.

ALGORITHM:
1)Initialize
-Choose a starting vertex (can be arbitrary) and add it to the minimum
spanning tree.
-Initialize a priority queue (min-heap) to store edges based on their weights.

2)Update Priority Queue:


-Add all edges connected to the chosen vertex to the priority queue.

3)Select Minimum Edge:


-Extract the edge with the minimum weight from the priority queue.

4)Update Minimum Spanning Tree:


-If the other endpoint of the selected edge is not in the minimum spanning
tree, add it to the tree.
-Update the priority queue with the edges connected to the newly added
vertex.
5)Repeat:
-Repeat steps 3-4 until all vertices are in the minimum spanning tree.

EXAMPLE:

Let a weighted graph be:


Step 1 - First, we have to choose a vertex from the above graph. Let's choose
B.

Step 2 - Now, we have to choose and add the shortest edge from vertex B.
There are two edges from vertex B that are B to C with weight 10 and edge B
to D with weight 4. Among the edges, the edge BD has the minimum weight.
So, add it to the MST.

Step 3 - Now, again, choose the edge with the minimum weight among all the
other edges. In this case, the edges DE and CD are such edges. Add them to
MST and explore the adjacent of C, i.e., E and A. So, select the edge DE and
add it to the MST.
Step 4 - Now, select the edge CD, and add it to the MST.

Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it
would create a cycle to the graph. So, choose the edge CA and add it to the
MST.

So, the graph produced in step 5 is the minimum spanning tree of the given
graph. The cost of the MST is 10 units

-HERE IS THE IMPLEMENTATION OF PRIMS ALGORITHM IN PYTHON:

You might also like