Scribd
Upload
2 views33 pages

Lecture 18 -Prims Algorithm

Prim's Algorithm is a greedy method for generating a minimum spanning tree (MST) from a weighted graph by adding edges one by one based on minimum weight. The algorithm starts with the minimum weight edge and continues to add edges that connect included nodes to excluded nodes while maintaining a tree structure. Efficient execution involves tracking the minimum weight edge for each excluded node using a node index.

Uploaded by

sthory790
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
2 views33 pages

Lecture 18 -Prims Algorithm

Prim's Algorithm is a greedy method for generating a minimum spanning tree (MST) from a weighted graph by adding edges one by one based on minimum weight. The algorithm starts with the minimum weight edge and continues to add edges that connect included nodes to excluded nodes while maintaining a tree structure. Efficient execution involves tracking the minimum weight edge for each excluded node using a node index.

Uploaded by

sthory790
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

PRIMS ALGORITHM

Spanning Tree
• Let G = (V, E) be the graph where V is the set of vertices, E is the set
of edges and |V|= n.
• The spanning tree G′= (V, E′) is a sub graph of G in which all the
vertices of graph G are connected with minimum number of
edges.
• The minimum number of edges required to correct all the vertices
of a graph G in n – 1.
• Spanning tree plays a very important role in designing efficient
algorithms.
Spanning Tree
• If we consider a weighted graph then all the spanning trees
generated from the graph have different weights.
• The weight of the spanning tree is the sum of its edges weights.
• The spanning tree with minimum weight is called minimum
spanning tree (MST).
Greedy Method for Generating Spanning Tree
• A greedy method to obtain the minimum spanning tree would
construct the tree edge by edge, where each edge is chosen
accounting to some optimization criterion.
• An obvious criterion would be to choose an edge which adds a
minimum weight to the total weight of the edges selected so far.
• There are two ways in which this criterion can be achieved.
Greedy Method for Generating Spanning Tree
First Method:
• The set of edges selected so far always forms a tree.
• The next edge to be added is such that not only it adds a minimum
weight, but also forms a tree with the previous edges.
• It can be shown that the algorithm results in a minimum cost tree;
this algorithm is called Prim’s algorithm.
Greedy Method for Generating Spanning Tree
Second Method
• The edges are considered in non decreasing order of weight;
• The set T of edges at each stage is such that it is possible to
complete T into a tree
• Thus T may not be a tree at all stages of the algorithm; this also
results in a minimum cost tree; this algorithm is called Kruskal’s
algorithm.
Prim’s Algorithm
• This algorithm starts with a tree that has only one edge, the minimum
weight edge.
• The edges (j, q) is added one by one such that node j is already
included, node q is not included and weight wt(j, q) is the minimum
amongst all the edges (x, y) for which x is in the tree and y is not.
• In order to execute this algorithm efficiently, we have a node index
near(j) associated with each node j that is not yet included in the tree.
• If a node is included in the tree, near(j) = 0. The node near(j) is selected
into the tree such that wt(j, near(j)) in the minimum amongst all
possible choices for near(j).

You might also like