Short Notes: Greedy Algorithms (Part-2) | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


Algorithms : Greedy Algorithms (Part - 2)
SPANNING TREE
A spanning tree is a subset of Graph G , which has all the vertices covered with 
minimum possible number of edges.
Let a Graph G has n vertices and e edges.
• Then Spanning tree T of Graph G contains n vertices and (n-1) edges.
• Spanning tree T has no cycles which is a tree.
Minimum Weight Spanning Tree (MST): It is a spanning tree where the total edge 
weight is minimal among all the possible spanning trees of the given graph G . Such 
spanning tree with minimum weight is called minimum weight spanning tree (MST).
• An MST is not necessarily unique.
Example: Consider the following graph G . Find the minimum weight spanning tree 
of G .
Page 2


Algorithms : Greedy Algorithms (Part - 2)
SPANNING TREE
A spanning tree is a subset of Graph G , which has all the vertices covered with 
minimum possible number of edges.
Let a Graph G has n vertices and e edges.
• Then Spanning tree T of Graph G contains n vertices and (n-1) edges.
• Spanning tree T has no cycles which is a tree.
Minimum Weight Spanning Tree (MST): It is a spanning tree where the total edge 
weight is minimal among all the possible spanning trees of the given graph G . Such 
spanning tree with minimum weight is called minimum weight spanning tree (MST).
• An MST is not necessarily unique.
Example: Consider the following graph G . Find the minimum weight spanning tree 
of G .
Spanning tree for the above graph G is:
There are two popular Greedy algorithms for finding the minimum spanning tree.
• Kruskal's Algorithm
• Prim's Algorithm
Kruskal's Algorithm
• It follows greedy approach to compute the minimum spanning tree.
• Kruskal's Algorithm computes minimum spanning tree by considering the 
edges in increasing order of weight.
• Intermediate result of kruskal's algorithm may be connected or disconnected 
graph.
• It can be implemented using Union find data structure.
Page 3


Algorithms : Greedy Algorithms (Part - 2)
SPANNING TREE
A spanning tree is a subset of Graph G , which has all the vertices covered with 
minimum possible number of edges.
Let a Graph G has n vertices and e edges.
• Then Spanning tree T of Graph G contains n vertices and (n-1) edges.
• Spanning tree T has no cycles which is a tree.
Minimum Weight Spanning Tree (MST): It is a spanning tree where the total edge 
weight is minimal among all the possible spanning trees of the given graph G . Such 
spanning tree with minimum weight is called minimum weight spanning tree (MST).
• An MST is not necessarily unique.
Example: Consider the following graph G . Find the minimum weight spanning tree 
of G .
Spanning tree for the above graph G is:
There are two popular Greedy algorithms for finding the minimum spanning tree.
• Kruskal's Algorithm
• Prim's Algorithm
Kruskal's Algorithm
• It follows greedy approach to compute the minimum spanning tree.
• Kruskal's Algorithm computes minimum spanning tree by considering the 
edges in increasing order of weight.
• Intermediate result of kruskal's algorithm may be connected or disconnected 
graph.
• It can be implemented using Union find data structure.
Procedure for Kruskal's algorithm:
1. Sort all edges in increasing weight order by generating min-heap for the 
edges.
2. Select an edge with minimum weight, i.e, delete the root from min heap.
3. If the edge does not create a cycle, add it to the spanning tree. Otherwise 
discard it.
4. Stop, when n - 1 edges have been added. Otherwise repeat step 2 to step 3.
Example of Kruskal's Algorithm :
Consider the following graph :
Now we will make the spanning tree step - by step,
1. Choose the minimum edge , i.e AC
2. Choose the next minimum , i.e BD
3. Repeat, next minimum , i.e BC
4. Next minimum , AD but this will create cycle , so discard it.
5. Similarly discard next CD , AB because they forms cycle.
6. At last include AE.
So , the final spanning tree is :
Page 4


Algorithms : Greedy Algorithms (Part - 2)
SPANNING TREE
A spanning tree is a subset of Graph G , which has all the vertices covered with 
minimum possible number of edges.
Let a Graph G has n vertices and e edges.
• Then Spanning tree T of Graph G contains n vertices and (n-1) edges.
• Spanning tree T has no cycles which is a tree.
Minimum Weight Spanning Tree (MST): It is a spanning tree where the total edge 
weight is minimal among all the possible spanning trees of the given graph G . Such 
spanning tree with minimum weight is called minimum weight spanning tree (MST).
• An MST is not necessarily unique.
Example: Consider the following graph G . Find the minimum weight spanning tree 
of G .
Spanning tree for the above graph G is:
There are two popular Greedy algorithms for finding the minimum spanning tree.
• Kruskal's Algorithm
• Prim's Algorithm
Kruskal's Algorithm
• It follows greedy approach to compute the minimum spanning tree.
• Kruskal's Algorithm computes minimum spanning tree by considering the 
edges in increasing order of weight.
• Intermediate result of kruskal's algorithm may be connected or disconnected 
graph.
• It can be implemented using Union find data structure.
Procedure for Kruskal's algorithm:
1. Sort all edges in increasing weight order by generating min-heap for the 
edges.
2. Select an edge with minimum weight, i.e, delete the root from min heap.
3. If the edge does not create a cycle, add it to the spanning tree. Otherwise 
discard it.
4. Stop, when n - 1 edges have been added. Otherwise repeat step 2 to step 3.
Example of Kruskal's Algorithm :
Consider the following graph :
Now we will make the spanning tree step - by step,
1. Choose the minimum edge , i.e AC
2. Choose the next minimum , i.e BD
3. Repeat, next minimum , i.e BC
4. Next minimum , AD but this will create cycle , so discard it.
5. Similarly discard next CD , AB because they forms cycle.
6. At last include AE.
So , the final spanning tree is :
E
70
Analysis of Kruskal's algorithm:
• Step 1: Build Heap for edges => 0(E)
• Step 2 : Delete the root and add in MST. => O(logE)
• Step 3 : Keep doing it until MST is formed.
BEST CASE : MST is formed by deleting only (V-1) edges.
Hence T(n)= 0(E)+(V-1)logE = E+VlogE 
we know, logE = O(logV) 
hence T(n) = 0(E+VlogV)
WORST CASE : MST if formed by deleting all edges from heap 
Hence T(n)= 0(E)+(ElogE)=ElogE 
hence T(n) = O(ElogE)
Prim's algorithm
• It can be implemented using priority queue.
• In this , the MST is generated vertex by vertex.
• Intermediate result of prim's algorithm always connected graph.
Pseudo code for Prim's algorithm:
We keep a priority queue filled with all the nodes that have not yet been spanned. 
The value of each of these nodes is equal to the smallest weight of the edges that 
connect it to a the partial spanning tree.
1. Initialize the Priority queue with all the nodes and set their key values to a 
number larger than any edge, and the parent of the root to nil. Set the key 
value of the root to 0. (Step 1 to 5)
2. While Priority queue is not empty do { Let u be the minimum value node in the 
queue; For every node v in u's adjacency list do { if v is in queue and the 
weight on the edge (u,v) is less than key value(v) { Set parent of v to u; Set key 
value(v) to weight of (u,v);} } } (Step 7 to 11)
Page 5


Algorithms : Greedy Algorithms (Part - 2)
SPANNING TREE
A spanning tree is a subset of Graph G , which has all the vertices covered with 
minimum possible number of edges.
Let a Graph G has n vertices and e edges.
• Then Spanning tree T of Graph G contains n vertices and (n-1) edges.
• Spanning tree T has no cycles which is a tree.
Minimum Weight Spanning Tree (MST): It is a spanning tree where the total edge 
weight is minimal among all the possible spanning trees of the given graph G . Such 
spanning tree with minimum weight is called minimum weight spanning tree (MST).
• An MST is not necessarily unique.
Example: Consider the following graph G . Find the minimum weight spanning tree 
of G .
Spanning tree for the above graph G is:
There are two popular Greedy algorithms for finding the minimum spanning tree.
• Kruskal's Algorithm
• Prim's Algorithm
Kruskal's Algorithm
• It follows greedy approach to compute the minimum spanning tree.
• Kruskal's Algorithm computes minimum spanning tree by considering the 
edges in increasing order of weight.
• Intermediate result of kruskal's algorithm may be connected or disconnected 
graph.
• It can be implemented using Union find data structure.
Procedure for Kruskal's algorithm:
1. Sort all edges in increasing weight order by generating min-heap for the 
edges.
2. Select an edge with minimum weight, i.e, delete the root from min heap.
3. If the edge does not create a cycle, add it to the spanning tree. Otherwise 
discard it.
4. Stop, when n - 1 edges have been added. Otherwise repeat step 2 to step 3.
Example of Kruskal's Algorithm :
Consider the following graph :
Now we will make the spanning tree step - by step,
1. Choose the minimum edge , i.e AC
2. Choose the next minimum , i.e BD
3. Repeat, next minimum , i.e BC
4. Next minimum , AD but this will create cycle , so discard it.
5. Similarly discard next CD , AB because they forms cycle.
6. At last include AE.
So , the final spanning tree is :
E
70
Analysis of Kruskal's algorithm:
• Step 1: Build Heap for edges => 0(E)
• Step 2 : Delete the root and add in MST. => O(logE)
• Step 3 : Keep doing it until MST is formed.
BEST CASE : MST is formed by deleting only (V-1) edges.
Hence T(n)= 0(E)+(V-1)logE = E+VlogE 
we know, logE = O(logV) 
hence T(n) = 0(E+VlogV)
WORST CASE : MST if formed by deleting all edges from heap 
Hence T(n)= 0(E)+(ElogE)=ElogE 
hence T(n) = O(ElogE)
Prim's algorithm
• It can be implemented using priority queue.
• In this , the MST is generated vertex by vertex.
• Intermediate result of prim's algorithm always connected graph.
Pseudo code for Prim's algorithm:
We keep a priority queue filled with all the nodes that have not yet been spanned. 
The value of each of these nodes is equal to the smallest weight of the edges that 
connect it to a the partial spanning tree.
1. Initialize the Priority queue with all the nodes and set their key values to a 
number larger than any edge, and the parent of the root to nil. Set the key 
value of the root to 0. (Step 1 to 5)
2. While Priority queue is not empty do { Let u be the minimum value node in the 
queue; For every node v in u's adjacency list do { if v is in queue and the 
weight on the edge (u,v) is less than key value(v) { Set parent of v to u; Set key 
value(v) to weight of (u,v);} } } (Step 7 to 11)
• Insert(u) puts v in the structure
• Extract-M inQ finds and returns the node with minimum key value
• Decrease-K e y(u, w) updates (decreases) the key of v
MST-PrimfC, w , r )
1 for each u £ P[G]
2 do k e y [u] d o
3 7t [u ] N I L
4 k e y | V] ¦ * — 0
5
Q + ¦ -V[C\
6 while Q ^ 0
7 do u < — Extract-M in(Q)
8 for each v £ A d j [ i(]
9 do if v G Q and w {u , v
10 then ir'v] *— u
11 k ey [ u ] - i — w { (w, ¦
Example of Prim's Algorithm :
Consider the following graph :
Now we will make the spanning tree step - by step,
Step 1 : Start from A 
Step 2 : AC will be selected 
Step 3 : BC will be selected 
Step 4 : BD will be selected
Step 5 : All other edges except AE will be rejected due to cycle formation. 
Final MST is :