3.

SPANNING TREE
A Poem
I think that I shall never see
a graph more lovely than a tree.
A tree whose crucial property
is loop-free connectivity.
A tree that must be sure to span
so packet can reach every LAN.
First, the root must be selected.
By ID, it is elected.
Least-cost paths from root are traced.
In the tree, these paths are placed.
A mesh is made by folks like me,
then bridges find a spanning tree.
Network Wiring Problem

Central office

3
Solution 1

Central office

Expensive!
Solution 2

Central office

Minimize the total length of wire connecting the customers

Minimum Spanning Tree
 Sub-graph dari undirected weighted graph G, yang
memenuhi :
 Tree  no cyclic
 Melingkupi semua node
 Total ‘biaya’ setiap link menghasilkan nilai yang
paling kecil diantara kemungkinan tree yang lain
 Bisa terdapat lebih dari satu MST dalam sebuah
graph
Aplikasi MST
 Clasic:
 Routing Paket, pengkabelan, desain saluran pipa,
desain jalan, dll
 Internet Distribution Content
Bagaimana membangun MST?

9 9
b b
a 2 6 a 2 6
d d
4 5 4 5
5 4 5 4
5 e 5 e
c c
Dijkstra
Initialization
a. Pick a vertex r to be the root
b. Set D(r) = 0, parent(r) = null
c. For all vertices v  V, v  r, set D(v) = 
d. Insert all vertices into priority queue P,
using distances as the keys
Prim’s Algoritma
 While P is not empty:

 1. Select the next vertex u to add to the tree

 u = P.deleteMin()

 2. Update the weight of each vertex w adjacent to u which is

not in the tree (i.e., w  P)
 If weight(u,w) < D(w),
 a. parent(w) = u
 b. D(w) = weight(u,w)
 c. Update the priority queue to reflect
 new distance for w
Walk-Through
2
Initialize array
3
10
F C K dv pv

A 7
4
3 A F  
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  
H F  
 2
Start with any node, say D
3
10
F C K dv pv

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

A 7
4
3 A
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
 2 Select node with minimum
distance
3
10
F C K dv pv

A 7
4
3 A
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
 2 Update distances of adjacent,
unselected nodes
3
10
F C K dv pv

A 7
4
3 A
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
 2 Select node with minimum
distance
3
10
F C K dv pv

A 7
4
3 A
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
 2 Update distances of adjacent,
unselected nodes
3
10
F C K dv pv

A 7
4
3 A
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
 2 Select node with minimum
distance
3
10
F C K dv pv

A 7
4
3 A
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
 2 Update distances of adjacent,
unselected nodes
3
10
F C K dv pv

A 7
4
3 A 10 F
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
 2 Select node with minimum
distance
3
10
F C K dv pv

A 7
4
3 A 10 F
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
 2 Update distances of adjacent,
unselected nodes
3
10
F C K dv pv

A 7
4
3 A 10 F
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
 2 Select node with minimum
distance
3
10
F C K dv pv

A 7
4
3 A 10 F
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
 2 Update distances of adjacent,
unselected nodes
3
10
F C K dv pv

A 7
4
3 A 4 H
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
 2 Select node with minimum
distance
3
10
F C K dv pv

A 7
4
3 A T 4 H
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
 2 Update distances of adjacent,
unselected nodes
3
10
F C K dv pv

A 7
4
3 A T 4 H
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
 2 Select node with minimum
distance
3
10
F C K dv pv

A 7
4
3 A T 4 H
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
 2 Cost of Minimum Spanning
Tree =  dv = 21
3
F C K dv pv

A 4
3 A T 4 H
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

Work with edges, rather than nodes

Two steps:
– Sort edges by increasing edge weight
– Select the first |V| – 1 edges that do not
generate a cycle
 Walk-Through
Consider an undirected, weight graph
3
10
F C
A 4
4
3
8
6
5
4
B D
4
H 1
2
3
G 3
E
 Sort the edges by increasing edge weight
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1 (B,E) 4
8 (B,F) 4
6 (D,G) 2
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
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

Accepting edge (E,G) would create a cycle

 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4 
8 (B,F) 4
6 (D,G) 2 
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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 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
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 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
 Select first |V|–1 edges which do not
generate a cycle
3
F C edge dv edge dv

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

}
3 (G,H) 3  (D,F) 6
G E (C,F) 3  (A,B) 8
not
considered
(B,C) 4  (A,F) 10

Done
Total Cost =  dv = 21