Spanning Tree

Course Code: CSC 2106 Course Title: Data Structure (Theory)

Dept. of Computer Science

Faculty of Science and Technology

Lecture No: 12.1 Week No: 12 Semester: Fall 2020-2021

Lecturer: MAHFUJUR RAHMAN, [email protected]
Lecture Outline

1. Spanning Tree
2. Minimum Spanning Tree
3. Prim’s Algorithm
4. Kruskal’s Algorithm
Spanning Tree

A spanning tree of G is a subgraph which is a tree

contains all vertices of G

 How many edges

are there in a
spanning tree, if
there are V
vertices? (v-1)
Minimum Spanning Trees (MST)

 Undirected, connected graph

 G = (V,E)
 Weight W
Minimum Spanning Trees (MST)

 Undirected, connected graph

G = (V,E)

 Weight W

 Spanning tree: A spanning tree is a sub-graph of

a graph that contains or connects all the vertices
and has no cycle.
Minimum Spanning Trees (MST)

 Undirected, connected graph

G = (V,E)

 Weight W

 Minimum spanning tree (MST): Spanning tree where

total weight of the tree is minimum.
Applications of Minimum Spanning Tree

 Consider n stations are to be linked using a communication network & laying of

communication links between any two stations involves a cost.
The ideal solution would be to extract a subgraph termed as minimum cost spanning
tree.
 Suppose you want to construct highways or railroads spanning several cities then we
can use the concept of minimum spanning trees.
 Designing Local Area Networks.
 Laying pipelines connecting offshore drilling sites, refineries and consumer markets.
 Suppose you want to apply a set of houses with
 Electric Power
 Water
 Telephone lines
 Sewage lines
To reduce cost, you can connect houses with minimum cost spanning trees.
Algorithms for Obtaining the MST

 Prim's Algorithm

 Kruskal's Algorithm
Prim's Algorithm

 Vertex based algorithm

 Grows a single MST T one vertex at a time

 The set S covers the portion of T that was already computed

 Annotate all vertices v outside of the set S. The minimum weight of an edge
that connects v to a vertex in S is w.
(w = ¥ if no edge exists)
Prim's Algorithm
 T = a spanning tree containing a single node s;
E = set of edges adjacent to s;
while T does not contain all the nodes {
 remove an edge (v, w) of lowest cost from E
 if w is already in T then discard edge (v, w)
 else {
 add edge (v, w) and node w to T
 add to E the edges adjacent to w
 }

 }
 An edge of lowest cost can be found with a priority queue
 Testing for a cycle is automatic
 Hence, Prim’s algorithm is far simpler to implement than Kruskal’s algorithm
Prim's Algorithm

2
Initialize array

3
F C K dv pv
10
A 7 3 A F  
8 4
18 B F  
4
B D
9 C F  
10
H D F  
2 25
3 E F  
G E
7 F F  
G F  
H F  
Prim's Algorithm

2
Start with any node, say D

3
F C K dv pv
10
A 7 3 A
8 4
18 B
4
B D
9 C
10
H D T 0 
2 25
3 E
G E
7 F
G
H
Prim's Algorithm
Update distances of
adjacent, unselected nodes

3
F C K dv pv
10
A 7 3 A
8 4
18 B
4
B D
9 C 3 D
10
H D T 0 
2 25
3 E 25 D
G E
7 F 18 D
G 2 D
H
Prim's Algorithm

2 Select node with minimum

distance
3
F C K dv pv
10
A 7 3 A
8 4
18 B
4
B D
9 C 3 D
10
H D T 0 
2 25
3 E 25 D
G E
7 F 18 D
G T 2 D
H
Prim's Algorithm
Update distances of
adjacent, unselected nodes
2

3
F C K dv pv
10
A 7 3 A
8 4
18 B
4
B D
9 C 3 D
10
H D T 0 
2 25
3 E 7 G
G E
7 F 18 D
G T 2 D
H 3 G
Prim's Algorithm

Select node with minimum

2 distance
3
F C K dv pv
10
A 7 3 A
8 4
18 B
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E 7 G
G E
7 F 18 D
G T 2 D
H 3 G
Prim's Algorithm
Update distances of
adjacent, unselected nodes
2

3
F C K dv pv
10
A 7 3 A
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E 7 G
G E
7 F 3 C
G T 2 D
H 3 G
Prim's Algorithm
Select node with minimum
distance
2

3
F C K dv pv
10
A 7 3 A
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E 7 G
G E
7 F T 3 C
G T 2 D
H 3 G
Prim's Algorithm
Update distances of
adjacent, unselected nodes
2

3
F C K dv pv
10
A 7 3 A 10 F
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E 2 F
G E
7 F T 3 C
G T 2 D
H 3 G
Prim's Algorithm

2 Select node with minimum

distance
3
F C K dv pv
10
A 7 3 A 10 F
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E T 2 F
G E
7 F T 3 C
G T 2 D
H 3 G
Prim's Algorithm
Update distances of
adjacent, unselected nodes
2

3
F C K dv pv
10
A 7 3 A 10 F
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E T 2 F
G E
7 F T 3 C
G T 2 D
H 3 G
Table entries unchanged
Prim's Algorithm
Select node with minimum
distance
2

3
F C K dv pv
10
A 7 3 A 10 F
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E T 2 F
G E
7 F T 3 C
G T 2 D
H T 3 G
Prim's Algorithm
Update distances of
adjacent, unselected nodes
2

3
F C K dv pv
10
A 7 3 A 4 H
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E T 2 F
G E
7 F T 3 C
G T 2 D
H T 3 G
Prim's Algorithm
Select node with minimum
2 distance
3
F C K dv pv
10
A 7 3 A T 4 H
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E T 2 F
G E
7 F T 3 C
G T 2 D
H T 3 G
Prim's Algorithm
Update distances of
adjacent, unselected nodes
2

3
F C K dv pv
10
A 7 3 A T 4 H
8 4
18 B 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E T 2 F
G E
7 F T 3 C
G T 2 D
H T 3 G
Table entries unchanged
Prim's Algorithm

Select node with minimum

distance
2

3
F C K dv pv
10
A 7 3 A T 4 H
8 4
18 B T 4 C
4
B D
9 C T 3 D
10
H D T 0 
2 25
3 E T 2 F
G E
7 F T 3 C
G T 2 D
H T 3 G
Prim's Algorithm

Cost of Minimum Spanning Tree =

 dv = 21
2

3
F C K dv pv
A 3 A T 4 H
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
Kruskal's Algorithm

 Edge based algorithm

 Add edges one at a time in increasing weight order.

 The algorithm maintains S: a forest of trees.

 An edge is accepted if it connects vertices of distinct

trees (the cut respects S) and does not create any cycle.
Kruskal’s algorithm
 T = empty spanning tree;
E = set of edges;
N = number of nodes in graph;

 while T has fewer than N - 1 edges {

 remove an edge (v, w) of lowest cost from E
 if adding (v, w) to T would create a cycle
 then discard (v, w)
 else add (v, w) to T

 }
 Finding an edge of lowest cost can be done just by sorting
the edges
 Efficient testing for a cycle requires a fairly complex
algorithm (UNION-FIND) which we don’t cover in this
course
Kruskal’s algorithm

Consider an undirected, weight graph

3
F C
10
A 4 3
8 4
6
5
B D
4
4
H
2 1
3
G E
3
Kruskal’s algorithm

Sort the edges by increasing edge weight

3
F C edge dv edge dv
10
A 4 3 (D,E) 1 (B,E) 4
8 4
6 (D,G) 2 (B,F) 4
5
B D (E,G) 3 (B,H) 4
4
4
H (C,D) 3 (A,H) 5
2 1
3 (G,H) 3 (D,F) 6
G E (A,B) 8
3 (C,F) 3
(B,C) 4 (A,F) 10
Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle

3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2 (B,F) 4
5
B D (E,G) 3 (B,H) 4
4
4
H (C,D) 3 (A,H) 5
2 1
3 (G,H) 3 (D,F) 6
G E (A,B) 8
3 (C,F) 3
(B,C) 4 (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
B D (E,G) 3 (B,H) 4
4
4
H (C,D) 3 (A,H) 5
2 1
3 (G,H) 3 (D,F) 6
G E (A,B) 8
3 (C,F) 3
(B,C) 4 (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
B D (E,G) 3 (B,H) 4
4 
4
H (C,D) 3 (A,H) 5
2 1
3 (G,H) 3 (D,F) 6
G E (A,B) 8
3 (C,F) 3
(B,C) 4 (A,F) 10

Accepting edge (E,G) would create a cycle

Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
B D (E,G) 3 (B,H) 4
4 
4
H (C,D) 3  (A,H) 5
2 1
3 (G,H) 3 (D,F) 6
G E (A,B) 8
3 (C,F) 3
(B,C) 4 (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
B D (E,G) 3 (B,H) 4
4 
4
H (C,D) 3  (A,H) 5
2 1
3 (G,H) 3  (D,F) 6
G E (A,B) 8
3 (C,F) 3
(B,C) 4 (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
B D (E,G) 3 (B,H) 4
4 
4
H (C,D) 3  (A,H) 5
2 1
3 (G,H) 3  (D,F) 6
G E (A,B) 8
3 (C,F) 3 
(B,C) 4 (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4
8 4
6 (D,G) 2  (B,F) 4
5
B D (E,G) 3 (B,H) 4
4 
4
H (C,D) 3  (A,H) 5
2 1
3 (G,H) 3  (D,F) 6
G E (A,B) 8
3 (C,F) 3 
(B,C) 4  (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4 
8 4
6 (D,G) 2  (B,F) 4
5
B D (E,G) 3 (B,H) 4
4 
4
H (C,D) 3  (A,H) 5
2 1
3 (G,H) 3  (D,F) 6
G E (A,B) 8
3 (C,F) 3 
(B,C) 4  (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4 
8 4
6 (D,G) 2  (B,F) 4 
5
B D (E,G) 3 (B,H) 4
4 
4
H (C,D) 3  (A,H) 5
2 1
3 (G,H) 3  (D,F) 6
G E (A,B) 8
3 (C,F) 3 
(B,C) 4  (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4 
8 4
6 (D,G) 2  (B,F) 4 
5
B D (E,G) 3 (B,H) 4
4  
4
H (C,D) 3  (A,H) 5
2 1
3 (G,H) 3  (D,F) 6
G E (A,B) 8
3 (C,F) 3 
(B,C) 4  (A,F) 10
Kruskal’s algorithm

Select first |V|–1 edges which do not

generate a cycle
3
F C edge dv edge dv
10
A 4 3 (D,E) 1  (B,E) 4 
8 4
6 (D,G) 2  (B,F) 4 
5
B D (E,G) 3 (B,H) 4
4  
4
H (C,D) 3  (A,H) 5 
2 1
3 (G,H) 3  (D,F) 6
G E (A,B) 8
3 (C,F) 3 
(B,C) 4  (A,F) 10
Kruskal’s algorithm
Select first |V|–1 edges which do not
generate a cycle
3
F C edge dv edge dv

A 3 (D,E) 1  (B,E) 4 
4
(D,G) 2  (B,F) 4 
5
B D (E,G) 3 (B,H) 4
 
H (C,D) 3  (A,H) 5 
1

}
2
3 (G,H) 3  (D,F) 6
G E not
(C,F) 3  (A,B) 8 considered
(B,C) 4  (A,F) 10
Done
Total Cost =  dv = 21
Books

 “Schaum's Outline of Data Structures with C++”. By John R. Hubbard (Can be

found in university Library)
 “Data Structures and Program Design”, Robert L. Kruse, 3rd Edition, 1996.
 “Data structures, algorithms and performance”, D. Wood, Addison-Wesley, 1993
 “Advanced Data Structures”, Peter Brass, Cambridge University Press, 2008
 “Data Structures and Algorithm Analysis”, Edition 3.2 (C++ Version), Clifford A.
Shaffer, Virginia Tech, Blacksburg, VA 24061 January 2, 2012
 “C++ Data Structures”, Nell Dale and David Teague, Jones and Bartlett Publishers,
2001.
 “Data Structures and Algorithms with Object-Oriented Design Patterns in C++”,
Bruno R. Preiss,
References

1. https://en.wikipedia.org/wiki/Data_structure
2. https://visualgo.net/en/mst?slide=1