Minimum Spanning Trees - PPT Computer Science Engineering (CSE) Notes | EduRev

Computer Science Engineering (CSE) : Minimum Spanning Trees - PPT Computer Science Engineering (CSE) Notes | EduRev

 Page 1


Analysis of Algorithms 
CS 477/677 
Minimum Spanning Trees (MST) 
Instructor: George Bebis 
 
Chapter 23 
Page 2


Analysis of Algorithms 
CS 477/677 
Minimum Spanning Trees (MST) 
Instructor: George Bebis 
 
Chapter 23 
2 
Minimum Spanning Trees 
• Spanning Tree 
– A tree (i.e., connected, acyclic graph) which contains 
all the vertices of the graph 
• Minimum Spanning Tree 
– Spanning tree with the minimum sum of weights 
 
 
 
 
• Spanning forest 
– If a graph is not connected, then there is a spanning 
tree for each connected component of the graph 
a 
b c d 
e 
g g f 
i 
4 
8 
7 
8 
11 
1 
2 
7 
2 
4 
14 
9 
10 
6 
Page 3


Analysis of Algorithms 
CS 477/677 
Minimum Spanning Trees (MST) 
Instructor: George Bebis 
 
Chapter 23 
2 
Minimum Spanning Trees 
• Spanning Tree 
– A tree (i.e., connected, acyclic graph) which contains 
all the vertices of the graph 
• Minimum Spanning Tree 
– Spanning tree with the minimum sum of weights 
 
 
 
 
• Spanning forest 
– If a graph is not connected, then there is a spanning 
tree for each connected component of the graph 
a 
b c d 
e 
g g f 
i 
4 
8 
7 
8 
11 
1 
2 
7 
2 
4 
14 
9 
10 
6 
3 
Applications of MST 
– Find the least expensive way to connect a set of 
cities, terminals, computers, etc. 
 
Page 4


Analysis of Algorithms 
CS 477/677 
Minimum Spanning Trees (MST) 
Instructor: George Bebis 
 
Chapter 23 
2 
Minimum Spanning Trees 
• Spanning Tree 
– A tree (i.e., connected, acyclic graph) which contains 
all the vertices of the graph 
• Minimum Spanning Tree 
– Spanning tree with the minimum sum of weights 
 
 
 
 
• Spanning forest 
– If a graph is not connected, then there is a spanning 
tree for each connected component of the graph 
a 
b c d 
e 
g g f 
i 
4 
8 
7 
8 
11 
1 
2 
7 
2 
4 
14 
9 
10 
6 
3 
Applications of MST 
– Find the least expensive way to connect a set of 
cities, terminals, computers, etc. 
 
4 
Example 
Problem 
• A town has a set of houses  
 and a set of roads 
• A road connects 2 and only  
 2 houses 
• A road connecting houses u and v has a repair  
      cost w(u, v) 
Goal: Repair enough (and no more) roads such 
that: 
1. Everyone stays connected  
 i.e., can reach every house from all other houses 
2.   Total repair cost is minimum 
a 
b c d 
e 
h g f 
i 
4 
8 
7 
8 
11 
1 
2 
7 
2 
4 
14 
9 
10 
6 
Page 5


Analysis of Algorithms 
CS 477/677 
Minimum Spanning Trees (MST) 
Instructor: George Bebis 
 
Chapter 23 
2 
Minimum Spanning Trees 
• Spanning Tree 
– A tree (i.e., connected, acyclic graph) which contains 
all the vertices of the graph 
• Minimum Spanning Tree 
– Spanning tree with the minimum sum of weights 
 
 
 
 
• Spanning forest 
– If a graph is not connected, then there is a spanning 
tree for each connected component of the graph 
a 
b c d 
e 
g g f 
i 
4 
8 
7 
8 
11 
1 
2 
7 
2 
4 
14 
9 
10 
6 
3 
Applications of MST 
– Find the least expensive way to connect a set of 
cities, terminals, computers, etc. 
 
4 
Example 
Problem 
• A town has a set of houses  
 and a set of roads 
• A road connects 2 and only  
 2 houses 
• A road connecting houses u and v has a repair  
      cost w(u, v) 
Goal: Repair enough (and no more) roads such 
that: 
1. Everyone stays connected  
 i.e., can reach every house from all other houses 
2.   Total repair cost is minimum 
a 
b c d 
e 
h g f 
i 
4 
8 
7 
8 
11 
1 
2 
7 
2 
4 
14 
9 
10 
6 
5 
Minimum Spanning Trees 
• A connected, undirected graph: 
– Vertices = houses,       Edges = roads 
• A weight w(u, v) on each edge (u, v) ? E 
a 
b c d 
e 
h g f 
i 
4 
8 
7 
8 
11 
1 
2 
7 
2 
4 
14 
9 
10 
6 
Find T ? E such that: 
1. T connects all vertices 
2. w(T) = S
(u,v) ?T
 w(u, v) is  
 minimized 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Exam

,

Previous Year Questions with Solutions

,

ppt

,

pdf

,

MCQs

,

mock tests for examination

,

Minimum Spanning Trees - PPT Computer Science Engineering (CSE) Notes | EduRev

,

shortcuts and tricks

,

Sample Paper

,

Minimum Spanning Trees - PPT Computer Science Engineering (CSE) Notes | EduRev

,

Summary

,

video lectures

,

Viva Questions

,

past year papers

,

Objective type Questions

,

Free

,

study material

,

Semester Notes

,

Extra Questions

,

practice quizzes

,

Important questions

,

Minimum Spanning Trees - PPT Computer Science Engineering (CSE) Notes | EduRev

;