# Greedy Algorithms (Part - 2) Study Notes for GATE & Computer Science Engineering Exams

By Mukesh Kumar|Updated : December 12th, 2021

## SPANNING TREE

A spanning tree can be defined as a subset of Graph G, which has all the vertices covered with minimum possible number of edges.

Let us suppose a Graph G which has n number of vertices and e number of 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.

Here we are providing the complete study notes on the Greedy Algorithms (Part - 2) for the preparation of GATE, Computer Science Engineering Exam.

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. The Spanning tree for the above graph G can be designed as: 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 : ### Analysis of Kruskal's algorithm:

• Step 1: Build Heap for edges => O(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, Time complexity, T(n)= O(E)+(V-1)logE = E+VlogE

we know that , logE = O(logV)

So, the time complexity of Kruskal's Alogrithm is, T(n) = O(E+VlogV)

WORST CASE : MST if formed by deleting all edges from heap

Hence T(n)= O(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 that is filled with all the nodes that have not yet been spanned. Now, we take the value of each of these nodes which is equal to the minimum weight of the edges that connect these nodes to 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) ### 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 : ### Analysis of Prim's Algorithm

• Step 1 to Step 3: Takes O(|V|) time.
• Step 6 to Step 11: Takes O(|V| log |V|) + O(|E| log |V|); Here Extract Minimum operation at step 7 takes O(log |V|), and Updating queue (Decrease key operation)  from step 9 to step 11 also takes log |V| time using binary heap.
• Time complexity for Prim's algorithm (using binary heap as above) is O (|E| log |V|).
• If Prim's algorithm implemented using fibonacci heap, then time complexity is O(|E|+ |V| log |V|).
• If Prim's algorithm implemented using adjacency list, then time complexity is O(|V|2).

## DIJKSTRA's Algorithm :

This algorithm is used to find shortest distance from a specific node to all other nodes. Dijkstra algorithm's working is almost same as Prim's algorithm.

### Pseudo code for Dijsktra's algorithm:

• First set the distance of all nodes as infinity from a specific vertex
• Then start by choosing the minimum weighted edge from that vertex and update its distnace.
• Follow the same step until the distance for all nodes is discovered. ### Example of Dijkstra's Algorithm : ### Analysis of Dijkstra's Algorithm :

Dijkstra Algorithm works almost same as Prim's algorithm and have only some slight changes.

• First build heap of vertices.
• Choose minimum from min heap and insert in Dijsktra's graph.
• Perform Decrease key operation.

T(n) = O(V) + VlogV + ElogV

= O(V+E)logV

So that's all about Spanning trees and 3 algorithms : Kruskal's , Prim's and Dijsktra's.

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:

Thanks

write a comment   GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com