Summarize the following text to main points and sub-points and make detailed explain for them:

CS311 
Algorithm Design and 
Analysis
LECTURE 10 : GRAPH ALGORITHMS (2)
Contents
▪Minimum Spanning Tree
▪Kruskal’s Algorithm
▪Prim’s Algorithm
▪Kruskal’s Algorithm Versus Prim’s Algorithm
ALGORITHM DESIGN AND ANALYSIS
2
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)
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
Goal: Repair roads such that:   
1.
Everyone stays connected, i.e., can reach every house from all other houses
2.
Total repair cost is minimum
ALGORITHM DESIGN AND ANALYSIS
3
Problem
A connected, undirected graph where  Vertices = houses, Edges = roads.
A weight w(u, v) on each edge (u, v)  E
Find T  E such that:         1.  T connects all vertices
                                              2.   w(T) = Σ(u,v)T w(u, v) is minimized
ALGORITHM DESIGN AND ANALYSIS
4
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
a
b
c
d
e
g
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
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
◦Number of edges in a MST=   |V| - 1
a
b
c
d
e
g
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
ALGORITHM DESIGN AND ANALYSIS
5
Minimum spanning tree
Let’s think about simple MSTs on this graph:
a
b
c
d
1
2
5
3
4
a
b
c
d
1
2
5
3
4
Not spanning ➔ d is not in T.
a
b
c
d
1
2
5
3
4
Not a tree ➔ has a cycle.
ALGORITHM DESIGN AND ANALYSIS
6
Minimum spanning tree
Spanning Tree
Cost = 8
a
b
c
d
1
2
5
3
4
a
b
c
d
1
2
3
3
4
Spanning Tree
Cost = 8
a
b
c
d
1
2
3
3
4
Spanning Tree
Cost = 6
MST
ALGORITHM DESIGN AND ANALYSIS
7
Kruskal’s Algorithm
▪ Kruskal’s algorithm is a “greedy” algorithm.
▪ Creates a forest of trees. 
▪ Initially the forest consists of n single node trees (and no edges). 
▪ At each step, we add one safe edge (the cheapest one) so that 
    it joins two trees together. 
▪ Two steps:
– Sort edges by increasing edge weight
– Select the first |V| – 1 edges that do not generate a cycle
ALGORITHM DESIGN AND ANALYSIS
8
u
v
tree1
tree2
Example:
Consider an undirected, weight graph
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
Sort the edges by increasing edge weight
edge
dv
(D,E)
1
(D,G)
2
(E,G)
3
(C,D)
3
(G,H)
3 
(C,F)
3
(B,C)
4
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2
(E,G)
3
(C,D)
3
(G,H)
3 
(C,F)
3
(B,C)
4
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3
(C,D)
3
(G,H)
3 
(C,F)
3
(B,C)
4
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3
(G,H)
3 
(C,F)
3
(B,C)
4
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Accepting edge (E,G) would create a cycle
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 
(C,F)
3
(B,C)
4
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3
(B,C)
4
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3

(B,C)
4
5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3

(B,C)
4

5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4
(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3

(B,C)
4

5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4

(B,F)
4
(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3

(B,C)
4

5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4

(B,F)
4

(B,H)
4
(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3

(B,C)
4

5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4

(B,F)
4

(B,H)
4

(A,H)
5
(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3

(B,C)
4

5
1
A
H
B
F
E
D
C
G
3
2
4
6
3
4
3
4
8
4
3
10
edge
dv
(B,E)
4

(B,F)
4

(B,H)
4

(A,H)
5

(D,F)
6
(A,B)
8
(A,F)
10
Example:
Select first |V|–1 edges which do not 
generate a cycle
edge
dv
(D,E)
1

(D,G)
2

(E,G)
3

(C,D)
3

(G,H)
3 

(C,F)
3

(B,C)
4

5
1
A
H
B
F
E
D
C
G
2
3
3
3
edge
dv
(B,E)
4

(B,F)
4

(B,H)
4

(A,H)
5

(D,F)
6
(A,B)
8
(A,F)
10
Done
Total Cost =  dv = 21
4
}
not 
considered
Example:
Kruskal’s Algorithm Implementation
ALGORITHM DESIGN AND ANALYSIS
23
•
Uses a disjoint-set data structure to determine whether an edge connects vertices in 
different components.
•
Disjoint-set: is a data structure that tracks a set of elements partitioned into a number 
of disjoint (non-overlapping) subsets. 
•
If an element's parent pointer points to no other element, then the element is the root 
of a tree and is the representative member of its set.
•
Each element in the set that has a property representative member. 
ALGORITHM DESIGN AND ANALYSIS
24
Kruskal’s Algorithm Implementation
Kruskal’s Algorithm Implementation
MAKE-SET(u) – creates a new set whose only member is u
FIND-SET(u) – returns a representative element from the set that contains u
◦E.g.: Su = {r, s, t, u}
  FIND-SET(u) = r         FIND-SET(s) = r
◦FIND-SET  ->  return the same value for the elements of the same set.
UNION(u, v) –> unites the dynamic sets that contain u and v, say Su and Sv
◦E.g.: Su =  {r, s, t, u},  Sv = {v, x, y}  UNION (u, v) = {r, s, t, u, v, x, y}
Running time for FIND-SET and UNION depends on implementation. Can be O(lg n).
ALGORITHM DESIGN AND ANALYSIS
25
Kruskal’s Algorithm Implementation
Kruskal’s Algorithm Complexity
ALGORITHM DESIGN AND ANALYSIS
27
O(V)
O(E)
O(E lg E)
O(E lg E)
O(lg E)
O(lg E)
The total running time of Kruskal’s algorithm is O(E log E) = O(E log V)
Since E = O(V2), 
we have lg E=O(2 lg V) = O(lg V)
Prim’s Algorithm
▪  Prim’s algorithm has the property that the edges in the set A always form a single tree. 
▪  The tree starts from an arbitrary root vertex r and grows until it spans all the vertices in V 
▪  Each step adds to the tree A a light edge (a safe edge).
▪  When the algorithm terminates, the edges in A form a minimum spanning tree.
▪  Prim’s algorithm is a “greedy” algorithm
ALGORITHM DESIGN AND ANALYSIS
28
Prim’s Algorithm 
ALGORITHM DESIGN AND ANALYSIS
29
Example
 0              
Q = {a, b, c, d, e, f, g, h, i} 
VA = 
Extract-MIN(Q)  a
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
key [b] = 4  [b] = a
key [h] = 8  [h] = a
 
    4       8  
Q = {b, c, d, e, f, g, h, i}  VA = {a}
  = {a, #, #, #, #,#, a,#}
Extract-MIN(Q)  b















4

8
Example
4


8


8

a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
key [c] = 8  [c] = b
key [h] = 8  [h] = a ➔ unchanged
 
    8      8  
Q = {c, d, e, f, g, h, i}  VA = {a, b}
  = {b, #, #, #,#, a,#}
Extract-MIN(Q)  c
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
key [d] = 7  [d] = c
key [f] = 4  [f] = c
key [i] = 2   [i] = c
 
    7   4   8  2 
Q = {d, e,  f, g,  h, i}  VA = {a, b, c}
  = { c, #, c ,#, a, c}
Extract-MIN(Q)  i


4


8


8
7
4
2
Example
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
key [h] = 7  [h] = i
key [g] = 6  [g] = i
 
    7   4 6  8 
Q = {d, e, f, g, h}  VA = {a, b, c, i}
  = { c, #, c ,i, i}
Extract-MIN(Q)  f
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
key [g] = 2  [g] = f
key [d] = 7  [d] = c unchanged
key [e] = 10 
 [e] = f
 
    7 10 2 8 
Q = {d, e, g, h}  VA = {a, b, c, i, f}
  = { c, f ,f, i}
Extract-MIN(Q)  g
4
7

8

4
8
2
7
6
4
7

7
6
4
8
2
2
10
Example
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10
6
key [h] = 1  [h] = g
        7 10 1  
Q = {d, e, h}  VA = {a, b, c, i, f, g}
  = { c, f ,g}
Extract-MIN(Q)  h
a
b
c
d
e
h
g
f
i
4
8
7
8
11
1
2
7
2
4
14
9
10

Summary :