Minimum Spanning Tree: Algorithm Class Notes

Updated: Aug 18

Mobiprep has created last-minute notes for all topics of Algorithm to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Algorithm.

  1. Algorithm Basics

  2. Divide And Conquer

  3. Greedy Algorithm

  4. Dynamic Programming

  5. Shortest Path

  6. Backtracking

  7. Minimum Spanning Tree

  8. Maximum Flow

  9. Complexity Classes

Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.

  1. What is Minimum Spanning Tree

  2. How to find a minimum spanning tree?

  3. Discuss Application of Minimum Spanning Tree.

  4. Discuss Kruskal's Algorithm.

  5. Discuss Prim's Algorithm.


Minimum Spanning Tree


Question- 1) What is Minimum Spanning Tree

Answer: The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.

 

Question- 2) How to find a minimum spanning tree?

Answer:

  • Designing Local Area Networks.

  • Laying pipelines connecting offshore drilling sites, refineries and consumer markets.

  • Used to find approximate solutions for complex mathematical problems, NP-hard solutions like the Traveling Salesman Problem.

  • Cluster analysis.

  • Real-time face tracking and verification (i.e. locating human faces in a video stream).

  • Protocols in computer science to avoid network cycles.


 

Question- 3) Discuss Application of Minimum Spanning Tree

Answer: Minimum Spanning Tree (MST) problem: Given connected graph G with positive edge weights, find a min weight set of edges that connects all of the vertices.

MST is fundamental problem with diverse applications.


Network design.

  • telephone, electrical, hydraulic, TV cable, computer, road


Approximation algorithms for NP-hard problems.

  • traveling salesperson problem, Steiner tree


Indirect applications.

  • max bottleneck paths

  • LDPC codes for error correction

  • image registration with Renyi entropy

  • learning salient features for real-time face verification

  • reducing data storage in sequencing amino acids in a protein

  • model locality of particle interactions in turbulent fluid flows

  • auto-config protocol for Ethernet bridging to avoid cycles in a network


 

Question- 4) Discuss Kruskal's Algorithm

Answer: Kruskal's Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal's algorithm follows a greedy approach as in each iteration it finds an edge which has least weight and adds it to the growing spanning tree.

Algorithm:

  • Sort the graph edges with respect to their weights.

  • Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.

  • Only add edges which don't form a cycle, edges which connect only disconnected components.

Floyd's algorithm is a dynamic approach to find the shortest path between all the pairs of vertices in a weighted graph. The graph can be directed or undirected graph.


Pseudo Code :

n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
for i = 1 to n
for j = 1 to n
Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A

C program:


#include <stdio.h>

// defining the number of vertices
#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm
void floydWarshall(int graph[][nV]) {
int matrix[nV][nV], i, j, k;

for (i = 0; i < nV; i++)
for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];

// Adding vertices individually
for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {
for (int i = 0; i < nV; i++) {
for (int j = 0; j < nV; j++) {
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("\n");
}
}

int main() {
int graph[nV][nV] = {{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}};
floydWarshall(graph);
}



 

Question- 5) Discuss Prim's Algorithm.

Answer: Prim's Algorithm also uses the Greedy approach to find the minimum spanning tree. In Prim's Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal's, we add vertex to the growing spanning tree in Prim's.

Algorithm Steps:


  1. Remove all the loops and parallel edges.(keep the edges with least cost).

  2. Choose any node as a root node and add it to the spanning tree

  3. Add another vertex which is not in spanning tree and has least weight edge connected with the spanning tree.

  4. Repeat previous step until all the vertices of the graph added to the spanning tree

  5. Print the cost.


C code to implement Prims Algorithm:

#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]= {
0
}
,min,mincost=0,cost[10][10];
void main() {
clrscr();
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the adjacency matrix:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) {
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne<n) {
for (i=1,min=999;i<=n;i++)
for (j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0) {
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0) {
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
getch();
}

 



22 views0 comments

Recent Posts

See All