Introduction to MST

Estimated Time

1 hour

Introduction

Introduction video for MST

Prerequisites of the Experiment

This experiment requires you to have basic knowledge about :

And above all, a curiosity to learn and explore..!

Overview of the Experiment

  • The aim of this experiment is to understand the concept of MST, its time and space complexity against Kruskal's and Prim's algorithms
  • The experiment features a series of modules with video lectures, interactive demonstrations, simulations, hands-on practice exercises and quizzes for self analysis.

Learning Objectives of the Experiment

In this experiment, you will be able to do the following:
  • Given a connected Graph of some number of vertices , generate a Minimum Spanning Tree of graph by applying Kruskal's or Prim's algorithm
  • Demonstrate knowledge of time complexity of Kruskal's and Prim's by counting the number of operations involved in each iteration.
  • Compare Kruskal's and Prim's with other algorithms to find MST and realise Kruskal's and Prim's as the best ways to find MST.

Experiment Modules and Weightage

Module Weightage Expectation
Pre Test 5% Solve All Questions
MST 10% Understand concept of MST
Kruskal's Algorithm 20% Understand the Kruskal's Algorithm
Analysis of Kruskal's 15% Understand the time and space complexity
Prim's Algorithm 20% Understand the Prim's Algorithm
Analysis of Prim's 15% Understand the time and space complexity
Post Test 10% Solve all Questions

Pre-test of the Experiment

Estimated Time

10 minutes

Instructions for Pre-Test

  • Pretest includes questions on sorting, time complexity and space complexity, union-find algo Min-Max heap and Trees.
  • If you want to revise these topics before taking the quiz, go through the Basics Recap and Algorithm Recap modules first.
  • Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Quick look at Sorting, Time and Space Complexity,Trees and Graphs

What is Sorting?

Given a list of random numbers, sorting means ordering the numbers in either ascending or descending order. By default, we sort numbers in an ascending order.

Unsorted and Sorted Arrays

Picture shows sorted and unsorted array

Time and Space Complexity

  • Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input. Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.
  • Recall that suppose our input is an array of N elements, and our algorithm iterates through the array once, time complexity will be O(N). If I run two embedded loops to traverse the array N times, time complexity will be O(N2).

Trees and Graphs

  • Tree is an abstract data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
  • Graph with all vertices connectes is a connected graph and a tree that covers all vertices in graph is called spanning tree.
  • Graphs with a weight to edges is called weighted graph,Graphs with directions is directed graph.

Types of Graphs

Picture shows types of graphs

Quick look at Min-Heaps and Union-Find Algorithm

Min-Heaps

A Min-Heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.

Examples for Min-Heap and Non Min-Heaps

Picture shows types of graphs

Union-Find Algorithm

Union-Find algo has two important components Find and Union.
In Union-Find all elements of a tree are represented by head element in tree and when two trees are joined, the head of anyone of them is taken as head of new tree.
Find : Determine which subset (or) which tree the node belongs to.
Union : Join two subsets or two trees into same subset or tree.
When a new node is joined to a differnet tree or subset, both subsets together will be counted as a new subset or new tree such that the whole subset has a common head.
When a new edge is to be added, it has to be checked if both nodes of edge belong to same tree in which case circle is passed.

Visulalization of Union-Find

Picture helps for the visualization of Union-finds

A Quiz with Multiple Choice Questions

Q1. Which of these best describes an array?

(A) A data structure that shows a hierarchical behavior

(B) Container of objects of similar types

(C) Container of objects of mixed types

(D) All of the mentioned

An array is a data structure, which can store a fixed-size collection of elements of the same data type.

Q2. What is the time complexity of insertion at any point in an array?

(A) O(N)

(B) O(N^2)

(C) O(NLogN)

(D) None of these

Taking a general example,inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array,you will need to move n elements

Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

(A) X will always be a better choice for small inputs

(B) X will always be a better choice for large inputs

(C) Y will always be a better choice for small inputs

(D) X will always be a better choice for all inputs

Performance could be similar for small inputs, but definitely better for larger inputs

Q4. int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
What is the time and space complexity for the above code?

(A) O(N * M) time, O(1) space

(B) O(N + M) time, O(N + M) space

(C) O(N + M) time, O(1) space

(D) O(N * M) time, O(N + M) space

The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.

Q5. Choose one of the correct statements from the following?

(A) Trees may have cycles but not graphs.

(B) Graphs may have cycles but not trees

(C) Time complexity of Union-Find is O(n2)

(D) Time complexity of Union-Find is O(nlog(n))

Time complexity of Union-Find is O(log(N)).

Q6. What is the best possible order in which an array can be sorted?

(A) O(n2)

(B) O(nlog(n))

(C) O(n)

(D) O(log(n))

Best time complexity in which an array can be sorted in nlog(n).

MST

Estimated Time

15 minutes

Defining MST

Minimum Spannning Tree (MST) is defined for a weighted graph as the smallest weighted spanning tree Where Spanning Tree is a tree in graph such that it covers all edges of graph.

Understanding the Concept of MST

MST Visualization

Picture shows MSTs of different graphs

Observations based on MST

  • For a given graph there can be any number of MSTs but weight of MST to a graph is unique.
  • If all edge weights are distinct then MST to such graph is unique.
  • If given graph is a tree then graph itself is its MST.

Kruskal's Algorithm

Estimated Time

15 minutes

Learning Objectives of this Module :

In this module, we will :

  • Gain the intuition for Kruskal's Algorithm
  • Learn when and how to ad an edge to MST
  • Learn about the primitive Kruskal's algorithm
  • Practice the algorithm
  • Test your conceptual understanding with a short quiz

Understanding the Kruskal's Algorithm

How can we find MST using Kruskal's ?

In Kruskal's Algorithm, we take the fastest possible approach to create MST.
  • We first sort the edges of graph in increasing order.
  • Check the edges in sorted order if they should be in MST or not.
  • Whenever we see the newly taken edge making circle (checked by Union-find) (refer picture below), we do not keep it in MST or else we will proceed further.
  • We keep performing the above steps over the array again and again till all the edges are checked.

When should we add edge to mst?

Image shows scenarios to add and when not to.

Important Observations

Let's take note of a few important observations :

  • From the mentioned algorithm, we can conclude that after the Tth iteration, we will have the edges which should be in MST among T smallest places included in MST.
  • So, After N iterations we will have all edges which are to be in MST included in it.
  • Notice that after including N-1 edges in MST , MST will be finished.
  • Look at the picture below and work out the result of each iteration. See if it matches the picture, and notice which elements keep getting placed correctly after each iteration!

Step by Step Process for Kruskal's

image shows Step by Step Process for One Iteration

Demonstration for Kruskal's Algorithm

Kruskal's Algorithm

Video for Kruskal's Explanation

Concept of Kruskal's Algorithm

Let's have a final look at the consolidated algorithm to find MST of given graph:

  • STEP 1 : Sort the given edges
  • STEP 2 : Check each edge in sorted order if it forms a cycle with already selected edges. If not Add it to list of MST . If it does move to next edge.
  • STEP 3 : Run steps 1 and 2 till v-1 edges are selected (v=no.of.vertices).

Observations

  • From the mentioned Algo, we can conclude that after the Tth iteration, we will have the edges which should be in MST among T smallest places included in MST.
  • So, After N iterations we will have all edges which are to be in MST included in it.
  • Notice that after including N-1 edges in MST , MST will be finished.
  • Look at the picture below and work out the result of each iteration. See if it matches the picture, and notice which elements keep getting placed correctly after each iteration!

Iteration by Iteration Visualization of Kruskal's

image shows Iteration by Iteration Visualization of Kruskal's

Demonstration for Kruskal's

Demo : Kruskal's

Interactive artefact where user can click on Next Step or Previous Step to understand how the MST gets created at different levels.

Step by Step Practice for Kruskal's

Practice : Kruskal's

Interactive artefact where user can click on Next Step or Previous Step to understand how the edges add to MST levels

Hands-on Exercise for Kruskal's

Exercise : Kruskal's

Interactive artefact where user can generate questions and solve them, and then check the answers.

Revision Quiz for Kruskal's

Q1. When do we add an edge to MST while running Kruskal's ?

(A) When circle is formed by the new edge

(B) when the added edge dosen't create a circle

(C) when there is no circle at all

(D) if any circle exists

An edge is added to MST when it doesn't create a circle.

Q2. Which edge gets judged if it should or shouldn't be in MST after n iterations?

(A) Smallest edge

(B) Largest Edge

(C) Middle Edge in inc order

(D) No element

Q3. How many minimum edges should we add to MST to stop checking?

(A) V edges

(B) V-1 edges

(C) E edges

(D) E-1 edges

Since min spanning tree is a tree with V vertices it contains V-1 edges.

Q4. Consider the following statements.
S1. Kruskal’s algorithm might produce a non-minimal spanning tree.
S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.

(A) S1 is true but S2 is false

(B) Both S1 and S2 are false

(C) Both S1 and S2 are true

(D) S2 is true but S1 is false

In Kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components containing a vertex and adds the new edges. And Kruskal’s algorithm always finds the MST for the connected graph.

Q5. Which of the following is false about the Kruskal’s algorithm?

(A) It is a greedy algorithm

(B) It constructs MST by selecting edges in increasing order of their weights

(C) It can accept cycles in the MST

(D) It uses union-find data structure

Kruskal’s algorithm is a greedy algorithm to construct the MST of the given graph. It constructs the MST by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. So, using Kruskal’s algorithm is never formed.

Analysis of Kruskal's Algorithm

Estimated Time

10 minutes

Learning Objectives of this Module

In this module, we will be learning about :
  • Time and Space Complexity : We will learn about the running time of one iteration, and then extend it to N iterations to complete the sorting process.
  • Worst and Best cases : We will learn about Worst and Best cases in time complexity

Time and Space Complexity of Kruskal's

Running Time of Kruskal's

Lets assume that we are finding MST of a N vertices graph using Kruskal's.
  • To check edges we need to sort the given edges based on weights of edges. The best way to sort has a order of O(N log(N)).
  • To Check one edge if it needs to be in MST or not, we apply Union-find to check if it forms a circle with edges present and add to MST exactly once and apply Union-Find algorithm of order log(E).
  • Since we perform atmost N checks for a graph total complexity is O(Nlog(E)) for the checkings.
  • So, total complexity is O(Nlog(E)+Nlog(N))

Best and Worst Cases for Kruskal's

For regular Kruskal's, time complexity will be O(Nlog(E)+Nlog(N)) in all cases. For Kruskal's :
  • In best case scenario, we have N no cycles and we have to run N-1 iterations to determine MST.
  • Time complexity will be O((N-1)*log(E)+Elog(E)) in this case.
  • In worst case we will have to check all E edges . Time complexity in such case would be O(Elog(E)+Nlog(N))
Try out the demo below and look out for the number of checkings performed for different types of graphs!

Space Complexity of Kruskal's

While sorting, we need an extra array to store sorted array of edges (Space comlexity of O(E)), Another array for Union-Find of size O(E). So, total Space Complexity would be O(log(E)).

A Quiz with Multiple Choice Questions

Q1. What is the time complexity of Kruskal's algorithm?

(A) Best case is when given graph is a tree it self

(B) Best case O(n2)

(C) Worst case is when all edges are to be checked.

(D) Average case O(Nlog(E)+Nlog(N))

(E) A, C, D

All statements are self explanatory

Q2. Does Kruskal's need more than one MST ?

(A) Yes

(B) No

(C) Depend

(D) Can't say

Kruskal's generate only one MSt.

Q3. Which case is the best case Time Complexity of Kruskal's ?

(A) Max.no of edges and many cycles

(B) Min.no of edges and minimum cycles

(C) Min No.of edges with max no of cycles

(D) Can't Say

Complexity is min when no of edges and cycles are Minimum.

Q4. If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ?

(A) O(m logn)

(B) O(n)

(C) O(m)

(D) O(n logm)

O(m) as you are already given edge weights in sorted order. You just have to pick the edges in the increasing order and add it to the current spanning set if its addition does not result in a cycle else throw it away.

Q5. What is the best case Time Complexity of Kruskal's?

(A) O((N-1)log(E)+Elog(E))

(B) O((N)log(N)+Elog(E))

(C) O((N)log(E)+Elog(E))

(D) Cannot Determine

Given a tree then tree itself is MST.

Prim's Algorithm

Estimated Time

15 minutes

Learning Objectives of this Module :

In this module, we will :

  • Gain the intuition for Prim's Algorithm
  • Learn which edge to add to MST
  • Learn about the primitive Prim's algorithm
  • Practice the algorithm
  • Test your conceptual understanding with a short quiz

Understanding the Prim's Algorithm

How can we find MST using Prim's?

In Prim's algorithm, we take the fastest possible approach to create MST.
  • We first choose a random node of graph and add it to set of nodes which include in MST so far.
  • Add the edge weights of edges from newly added node in MST to its adjacent nodes which are not in MST so far.
  • Add the smallest weighted edge from Min-Heap into MST and include the respective node into MST.
  • We keep performing the above steps over the array again and again till all the edges checked.

Which edge should we add edge to MST?

Image shows scenarios which edge to add in MST

Important Observations

From the mentioned algorithm, we can conclude that:

  • After the Tth iteration, we will have T edges and T+1 nodes in MST.
  • So, after N iterations we will have all edges which are to be included in MST.
  • Look at the picture below and work out the result of each iteration. See if it matches the picture, and notice which elements keep getting placed correctly after each iteration!

Step by Step Process for One Iteration

image shows Step by Step Process for One Iteration

Demonstration for Prim's Algorithm

Prim's Algorithm

Video for Prim's

Prim's Algorithm

Let's have a final look at the consolidated algorithm to find mst of given graph:

  • STEP 1 : Choose a Node and add it to MST
  • STEP 2 : Check all of its adjacent nodes, if they are already present in MST or not if they are not present, add edge weight to that edge into Min-Heap.
  • STEP 3 : Add the smallest weighted edge and its node in Min-Heap to MST. Repeat step 2 and step 3 for Node added.
  • STEP 4 : Repeat step 2 , step 3 for recently added node.

Observations on Prim's

From the mentioned algorithm, we can conclude that,

  • After the Tth iteration, we will have the T edges and T+1 nodes in MST.
  • Notice that after N-1 iterations, all N nodes will be in MST.
  • Look at the picture below and work out the result of each iteration.

Iteration by Iteration Visualization of Prim's

image shows Iteration by Iteration Visualization of Prim's

Demonstration for Prim's

Demo : Prim's

Interactive artefact where user can click on Next Step or Previous Step to understand how the MST gets created at different levels.

Step by Step Practice for Prim's

Practice : Prim's

Interactive artefact where user can click on Next Step or Previous Step to understand how the edges add to MST levels.

Hands-on Exercise for Kruskal's

Exercise : Prim's

Interactive artefact where user can generate questions and solve them, and then check the answers. Ideas : find edge to be added etc

Revision Quiz for Prim's

Q1. When do we add vertex adjacent to newly added vertex to MST into Min-heap?

(A) If its present in Min-heap

(B) If its neither in MSt nor in Min-heap.

(C) If its already in MSt

(D) If its in Min-heap and MSt

Self-explanatory options

Q2. How many edges are present in MST after k iterations

(A) exactly K

(B) Less than K and atmost k

(C) More than k and atleast k

(D) Can't Say

Exactly 1 edge must be added in evrey iteration so its total of K edges.

Q3. Which of the following statements are false ?

(A) Prim's algo must be started from any vertex

(B) Prim's algo defenitely takes N-1 iterations to find MST

(C) Prim's algo started from a diferent vertices may give different MSts

(D) None of the above are false

(E) One of A,B,C is false

All A,B,C are correct.

Q4. Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density.

(A) d-array heap

(B) linear search

(C) fibonacci heap

(D) binary search

In Prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. This searching can be efficiently implemented using binary heap for dense graphs. And for graphs with greater density, Prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap).

Q5. Which of the following is false about Prim’s algorithm?

(A) It is a greedy algorithm

(B) It constructs MST by selecting edges in increasing order of their weights

(C) It never accepts cycles in the MST

(D) It can be implemented using the Fibonacci heap

Prim’s algorithm can be implemented using Fibonacci heap and it never accepts cycles. And Prim’s algorithm follows greedy approach. Prim’s algorithms span from one vertex to another

Analysis of Prim's Algorithm

Estimated Time

10 minutes

Learning Objectives of this Module

In this module, we will be learning about :

  • Time and Space Complexity : We will learn about the running time of one iteration, and then extend it to N iterations to complete the sorting process.
  • Worst and Best cases : We will learn about Worst and Best cases in time complexity

Time and Space Complexity of Prim's Algorithm

Running Time of Prim's Algorithm

Lets assume that we are given V vertices and E edges in a graph for which we need to find an MST.

  • To complete one iteration, we delete min node from Min-Heap and add some no.of edge weights to Min-Heap.
  • In total we delete V nodes from Min-Heap since we have V nodes in graph and in every iteration 1 edge and in total V-1 edges in MST are deleted and each deletion takes complexity of O(log(V)). And we add atmost E edges altogether where each adding takes complexity of O(log(V)).
  • So, totally complexity id O((V+E)Log(V)).

Best and Worst Cases for Prim's

  • Best case time complexity of Prim's is when the given graph is a tree itself and each node has minimum number of adjacent nodes.
  • Worst case time complexity would be when its a graph with V2 edges.

Space Complexity of Prim's

  • We need an array to know if a node is in MST or not. Space O(V).
  • We need an array to maintain Min-Heap. Space O(E).
  • So, Total space complexity is of order O(V+E)

Comparison with other algorithms

Comparing between Kruskal's and Prim's

Comparisons :

  • Other Algorithms : Prim's and Kruskal's are best possible algorithms to find MST and to complete the sorting process.
  • Comparision with Kruskal's : Kruskal have better running time if the number of edges is kept low.
    While Prim's has better running time if both the number of edges and nodes are kept low
    So, of course, the best algorithm depends on the graph and the cost of data structure.

Comparision graphs

Image shows comparision Graphs and tables

A Quiz with Multiple Choice Questions

Q1. What is the time complexity of Prim's algorithm?

(A) O((V+E)log(V))

(B) O(Vlog(V)+Elog(E))

(C) O(Vlog(E)+Elog(E))

(D) O(Elog(V)+Elog(E))

Time complexity of Prim's algorithm is O((V+E)log(V)).

Q2. Is Prim's algorithm always better than Kruskal's algorithm?

(A) Yes

(B) No

(C) Depend

(D) Can't say

It depends on V,E.

Q3. What is the best case Time Complexity of Prim's algorithm?

(A) O(V)

(B) O(n2)

(C) Somewhere in between N and N2

(D) None of the above

Complexity is E when given graph is a linear tree.

Q4. What is the worst case Time Complexity of Prim’s algorithm if adjacency matrix is used?

(A) O(log V)

(B) O(V2)

(C) O(E2)

(D) O(V log(E))

Use of adjacency matrix provides the simple implementation of the Prim’s algorithm. In Prim’s algorithm, we need to search for the edge with a minimum for that vertex. So, worst case time complexity will be O(V2), where V is the number of vertices.

Q5. Which of the following statements is true
S1 . Prim’s algorithm resembles Dijkstra’s algorithm.
S2 . Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.

(A) S1 and S2 both are false

(B) S1 is false and S2 is true

(C) Both S1 and S2 are true

(D) S2 is false and S1 is true.

In Prim’s algorithm, the MST is constructed starting from a single vertex and adding in new edges to the MST that link the partial tree to a new vertex outside of the MST. And Dijkstra’s algorithm also rely on the similar approach of finding the next closest vertex. So, Prim’s algorithm resembles Dijkstra’s algorithm.
Prim’s algorithm and Kruskal’s algorithm perform equally in case of the sparse graphs. But Kruskal’s algorithm is simpler and easy to work with. So, it is best suited for sparse graphs.

Post Test of the Experiment

Estimated Time

10 minutes

Instructions for Quiz

Post Test includes questions on entire experiment concepts. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

A Quiz with Multiple Choice Questions

Q1. Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?

(A) Every minimum spanning tree of G must contain emin.

(B) If emax is in a minimum spanning tree, then its removal must disconnect G

(C) No minimum spanning tree contains emax

(D) G has a unique minimum spanning tree

As edge weights are unique, there will be only one edge emin and that will be added to MST, therefore option (A) is always true.
As spanning tree has minimum number of edges, removal of any edge will disconnect the graph. Therefore, option (B) is also true.
As all edge weights are distinct, G will have a unique minimum spanning tree. So, option (D) is correct.
Option C is false as emax can be part of MST if other edges with lesser weights are creating cycle and number of edges before adding emax is less than (n-1).

Q2. What is the best case Time Complexity of Kruskal's?

(A) O((N-1)log(E)+Elog(E))

(B) O((N)log(N)+Elog(E))

(C) O((N)log(E)+Elog(E))

(D) Cannot Determine

Given a tree then tree itself is MST.

Q3. How many iterations of MST are required to run Kruskal's algorithm on a non-cyclic graph ?

(A) V

(B) V-1

(C) E

(D) E-1

MST has N-1 edges and since none forms a cycle MST will be obtained in N-1 iterations

Q4. What is the minimum and maximum number of MST's possible for a given connected undirected non cyclic graph?

(A) Min : 1, Max: 1

(B) Min : 1, Max :N

(C) Min : N, MAx : N

(D) MIN : 1, Max : E

There will only be one MST in given case.

Q5. Which of the following is false about Prim’s algorithm?

(A) It is started from an edge

(B) It constructs MSt in increasing order of their weights

(C) It never accepts cycles in MST

(D) It can be implemented using heaps

In Kruskal's MST is made with edges in increasing order and not in Prim's.

Further Readings and References of the Experiment

Explore More About MSTs

You can explore more about MST Experiment through following resources:


Useful Links :

Quizzes :