Minimum Spanning Tree
Uploaded by
Aditya TiwariMinimum Spanning Tree
Uploaded by
Aditya TiwariChapter 23
Minimum Spanning Trees
Minimum Spanning Trees
• Find a minimum-cost set of edges that connect all
vertices of a graph
• Applications
– Connect “nodes” with a minimum of “wire”
• Networking
• Circuit design
2
Minimum Spanning Trees
• Find a minimum-cost set of edges that connect all
vertices of a graph
• Applications
– Collect nearby nodes
• Clustering, taxonomy construction
3
Minimum Spanning Trees
• Find a minimum-cost set of edges that connect all
vertices of a graph
• Applications
– Approximating graphs
4
Minimum Spanning Trees
• A tree is an acyclic, undirected, connected graph
• A spanning tree of a graph is a tree containing all
vertices from the graph
• A minimum spanning tree is a spanning tree,
where the sum of the weights on the tree’s edges
are minimal
5
Minimum Spanning Trees
• A minimum spanning tree is a spanning tree,
where the sum of the weights on the tree’s edges
are minimal
6
Minimum Spanning Trees
• Problem formulation
– Given an undirected, weighted graph with
weights for each edge
– Find an acyclic subset that connects all of the
vertices and minimizes the total weight:
– The minimum spanning tree is
• Minimum spanning tree may be not unique (can be more than
one)
7
Minimum Spanning Trees
• Both Kruskal’s and Prim’s Algorithms work with
undirected graphs
• Both work with weighted and unweighted graphs but
are more interesting when edges are weighted
• Both are greedy algorithms that produce optimal
solutions
8
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
– Work with edges
– Two steps:
• Sort edges by increasing edge weight
• Select the first |V| - 1 edges that do not generate a cycle
– Walk through:
3
10 F C
4 3
A 4
8
6
5
4 B D
4
H 1
2
3
G 3 E
9
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Sort the edges by increasing edge weight
3
10 F C edge dv edge dv
4 3 (D,E) 1 (B,E) 4
A 4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H (C,D) 3 (A,H) 5
1
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
10
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
A 4 3 (D,E) 1 (B,E) 4
8 4
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H (C,D) 3 (A,H) 5
1
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
11
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
A 4 3 (D,E) 1 (B,E) 4
4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H (C,D) 3 (A,H) 5
1
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
12
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
A 4 3 (D,E) 1 (B,E) 4
4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H (C,D) 3 (A,H) 5
1
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
Accepting edge (E,G) would create a cycle
13
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
A 4 3 (D,E) 1 (B,E) 4
4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
14
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
A 4 3 (D,E) 1 (B,E) 4
4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
15
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
A 4 3 (D,E) 1 (B,E) 4
4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
16
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
A 4 3 (D,E) 1 (B,E) 4
4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
17
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
4 3 (D,E) 1 (B,E) 4
A 4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
18
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
4 3 (D,E) 1 (B,E) 4
A 4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
19
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
4 3 (D,E) 1 (B,E) 4
A 4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
20
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
10 F C edge dv edge dv
4 3 (D,E) 1 (B,E) 4
A 4
8
6 (D,G) 2 (B,F) 4
5
4 B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3 E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
21
Minimum Spanning Trees
• Solution 1: Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
F C edge dv edge dv
3 (D,E) 1 (B,E) 4
A 4
(D,G) 2 (B,F) 4
5
B D (E,G) 3 (B,H) 4
H (C,D) 3 (A,H) 5
considered
1
2
3 (G,H) 3 (D,F) 6
}
not
G E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10
Done
Total Cost = 21 22
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
– Work with nodes (instead of edges)
– Two steps
• Select node with minimum distance
• Update distances of adjacent, unselected nodes
– Walk through: 2
10 F C
7 3
A 4
8
18
4
9 B D
10
H 25
2
3
G 7 E 23
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
Initialize array
3
10 F C K dv pv
7 3 A F
A 4
8
18 B F
4
9 B D C F
10
H 25
D F
2
3 E F
G 7 E F F
G F
K : whether in the tree H F
dv : distance to the tree
pv : closest node that is in the tree 24
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
Start with any node, say D
3
10 F C K dv pv
7 3 A
A 4
8
18 B
4
9 B D C
10
H 25
D T 0
2
3 E
G 7 E F
G
H
25
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Update distances of
adjacent, unselected nodes
3
10 F C K dv pv
7 3 A
A 4
8
18 B
4
9 B D C 3 D
10
H 25
D T 0
2
3 E 25 D
G 7 E F 18 D
G 2 D
H
26
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Select node with
minimum distance
3
10 F C K dv pv
7 3 A
A 4
8
18 B
4
9 B D C 3 D
10
H 25
D T 0
2
3 E 25 D
G 7 E F 18 D
G T 2 D
H
27
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Update distances of
adjacent, unselected nodes
3
10 F C K dv pv
7 3 A
A 4
8
18 B
4
9 B D C 3 D
10
H 25
D T 0
2
3 E 7 G
G 7 E F 18 D
G T 2 D
H 3 G
28
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Select node with
minimum distance
3
10 F C K dv pv
7 3 A
A 4
8
18 B
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E 7 G
G 7 E F 18 D
G T 2 D
H 3 G
29
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Update distances of
adjacent, unselected nodes
3
10 F C K dv pv
7 3 A
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E 7 G
G 7 E F 3 C
G T 2 D
H 3 G
30
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Select node with
minimum distance
3
10 F C K dv pv
7 3 A
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E 7 G
G 7 E F T 3 C
G T 2 D
H 3 G
31
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Update distances of
adjacent, unselected nodes
3
10 F C K dv pv
7 3 A 10 F
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E 2 F
G 7 E F T 3 C
G T 2 D
H 3 G
32
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Select node with
minimum distance
3
10 F C K dv pv
7 3 A 10 F
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E T 2 F
G 7 E F T 3 C
G T 2 D
H 3 G
33
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Update distances of
adjacent, unselected nodes
3
10 F C K dv pv
7 3 A 10 F
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E T 2 F
G 7 E F T 3 C
G T 2 D
H 3 G
Table entries unchanged
34
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Select node with
minimum distance
3
10 F C K dv pv
7 3 A 10 F
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E T 2 F
G 7 E F T 3 C
G T 2 D
H T 3 G
35
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Update distances of
adjacent, unselected nodes
3
10 F C K dv pv
7 3 A 4 H
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E T 2 F
G 7 E F T 3 C
G T 2 D
H T 3 G
36
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Select node with
minimum distance
3
10 F C K dv pv
7 3 A T 4 H
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E T 2 F
G 7 E F T 3 C
G T 2 D
H T 3 G
37
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Update distances of
adjacent, unselected nodes
3
10 F C K dv pv
7 3 A T 4 H
A 4
8
18 B 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E T 2 F
G 7 E F T 3 C
G T 2 D
H T 3 G
Table entries unchanged
38
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Select node with
minimum distance
3
10 F C K dv pv
7 3 A T 4 H
A 4
8
18 B T 4 C
4
9 B D C T 3 D
10
H 25
D T 0
2
3 E T 2 F
G 7 E F T 3 C
G T 2 D
H T 3 G
39
Minimum Spanning Trees
• Solution 2: Prim’s algorithm
2 Cost of Minimum
Spanning Tree = 21
3
F C K dv pv
3 A T 4 H
A 4
B T 4 C
4
B D C T 3 D
H D T 0
2
3 E T 2 F
G E F T 3 C
G T 2 D
H T 3 G
Done 40
Minimum Spanning Trees
• Runtime
– When using binary heaps, the runtime of the Kruskal’s
algorithm is
– When using binary heaps, the runtime of the Prim’s
algorithm is
When using the Fibonacci heaps, the runtime of the
Prim’s algorithm becomes:
– So, when an undirected graph is dense (i.e., is
much small than ), the Prim’s algorithm is more
efficient
41
You might also like
- 17 Recursive Definitions and Structural InductionNo ratings yet17 Recursive Definitions and Structural Induction49 pages
- Minimum Cost Spanning Trees & ApplicationsNo ratings yetMinimum Cost Spanning Trees & Applications20 pages
- Demographics Segmentation Using Machine LearningNo ratings yetDemographics Segmentation Using Machine Learning8 pages
- Discrete Probability Distributions GuideNo ratings yetDiscrete Probability Distributions Guide20 pages
- Descriptive Analysis in R Programming - GeeksforGeeks-1-12No ratings yetDescriptive Analysis in R Programming - GeeksforGeeks-1-1212 pages
- Water Quality Prediction Using Machine Learning TechniqueNo ratings yetWater Quality Prediction Using Machine Learning Technique9 pages
- CHAPTER3 Continuous Probability DistributionNo ratings yetCHAPTER3 Continuous Probability Distribution56 pages
- Infant Mortality in Brazil A Survival Analysis Using Machine Learning Models7No ratings yetInfant Mortality in Brazil A Survival Analysis Using Machine Learning Models747 pages
- Linear Algebra Interview Questions and Answers - Sanfoundry 2No ratings yetLinear Algebra Interview Questions and Answers - Sanfoundry 21 page
- Mathematical Foundations in Image ProcessingNo ratings yetMathematical Foundations in Image Processing9 pages
- Federated Learning For Healthcare Informatics100% (1)Federated Learning For Healthcare Informatics19 pages
- Sat - 13.Pdf - Child Mortality Prediction Using Machine LearningNo ratings yetSat - 13.Pdf - Child Mortality Prediction Using Machine Learning11 pages
- Math Project: Karnataka Law Society's Gogte Institute of Technology, BelgaumNo ratings yetMath Project: Karnataka Law Society's Gogte Institute of Technology, Belgaum13 pages
- Minimum Spanning Tree: Presented By: Hinal LunagariyaNo ratings yetMinimum Spanning Tree: Presented By: Hinal Lunagariya30 pages
- Slide - Computational Complexity Theory 2.0No ratings yetSlide - Computational Complexity Theory 2.032 pages
- Class XI Computer Science Lesson 15 Logic Gates Part 2 Session 2023-'24No ratings yetClass XI Computer Science Lesson 15 Logic Gates Part 2 Session 2023-'2410 pages
- Design & Analysis of Algorithms - 88 MCQs With Answers - Part 1 - Department of Computer Engineers PDFNo ratings yetDesign & Analysis of Algorithms - 88 MCQs With Answers - Part 1 - Department of Computer Engineers PDF29 pages
- 10.1 Object-Oriented Programming in PythonNo ratings yet10.1 Object-Oriented Programming in Python23 pages
- Formal Languages, Automata, and Computability: Read Chapter 4 of The Book For Next TimeNo ratings yetFormal Languages, Automata, and Computability: Read Chapter 4 of The Book For Next Time37 pages
- MCQ Deep Learning Engineering Syllabus 1to 5 Unit ..No ratings yetMCQ Deep Learning Engineering Syllabus 1to 5 Unit ..2 pages
- Java Notes - TheTestingAcademy (Pramod Sir)No ratings yetJava Notes - TheTestingAcademy (Pramod Sir)3 pages
- A Simple Runge-Kutta 4 TH Order Python Algorithm: September 2020100% (1)A Simple Runge-Kutta 4 TH Order Python Algorithm: September 20205 pages
- K-Nearest-Neighbors Regression: I2n (X) I K 1 NNo ratings yetK-Nearest-Neighbors Regression: I2n (X) I K 1 N3 pages
