2.4 mst prim’s algorithm

Data Structure-mst prim’s algorithm

1. Spanning Trees and Minimum Spaning
Trees
spanning tree: (for connected, undirected
graph)
minimal set of edges that connect all
vertices (no cycles)
Minimum spanning tree: (for connected,
undirected and weighted graph)
minimal set of edges that connect all
vertices such that the sum of weights is
minimum.

2. Prim’s Algorithm
Similar to Dijkstra’s Algorithm except that d
v
records edge
weights, not path lengths

3. Prim's Algorithm
MST=NULL;
Select an edge of min weight and add it to MST
Iteration:
repeat till n-1 edges are added to MST
1.select an edge (v1,v2) such that v1 is in MST and v2 is
not in MST
2.add it to MST
Initialization:

4. Prims Algorithm
Input:
A connected weighted graph G = {V, E}
Initialization:
VMST = EMST = null
Select an aribitrary vertex, x, from V
add x to VMST
Iteration:
for i = 1 to |V|-1
select an edge v1,v2 with minimum weight such that
v1 V
∈
MST and v2 V \ V
∈
MST
Add v1 to VMST
Add (v1,v2) to EMST
return EMST

5. Walk-Through
Initialize array
K d
v
p
v
A F ¥ -
B F ¥ -
C F ¥ -
D F ¥ -
E F ¥ -
F F ¥ -
G F ¥ -
H F ¥ -
4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
2

6. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Start with any node, say D
K d
v
p
v
A
B
C
D T 0 -
E
F
G
H
2

7. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Update distances of
adjacent, unselected nodes
K d
v
p
v
A
B
C 3D
D T 0 -
E 25D
F 18D
G 2 D
H
2

8. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Select node with minimum
distance
K d
v
p
v
A
B
C 3D
D T 0 -
E 25D
F 18D
G T 2 D
H
2

9. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Update distances of
adjacent, unselected nodes
K d
v
p
v
A
B
C 3D
D T 0 -
E 7 G
F 18D
G T 2 D
H 3 G
2

10. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Select node with minimum
distance
K d
v
p
v
A
B
C T 3D
D T 0 -
E 7 G
F 18D
G T 2 D
H 3 G
2

11. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Update distances of
adjacent, unselected nodes
K d
v
p
v
A
B 4 C
C T 3D
D T 0 -
E 7 G
F 3 C
G T 2 D
H 3 G
2

12. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Select node with minimum
distance
K d
v
p
v
A
B 4 C
C T 3D
D T 0 -
E 7 G
F T 3 C
G T 2 D
H 3 G
2

13. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Update distances of
adjacent, unselected nodes
K d
v
p
v
A 10F
B 4 C
C T 3D
D T 0 -
E 2 F
F T 3 C
G T 2 D
H 3 G
2

14. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Select node with minimum
distance
K d
v
p
v
A 10F
B 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H 3 G
2

15. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Update distances of
adjacent, unselected nodes
K d
v
p
v
A 10F
B 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H 3 G
2
Table entries unchanged

16. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Select node with minimum
distance
K d
v
p
v
A 10F
B 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H T 3 G
2

17. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Update distances of
adjacent, unselected nodes
K d
v
p
v
A 4 H
B 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H T 3 G
2

18. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Select node with minimum
distance
K d
v
p
v
A T 4 H
B 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H T 3 G
2

19. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Update distances of
adjacent, unselected nodes
K d
v
p
v
A T 4 H
B 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H T 3 G
2
Table entries unchanged

20. 4
25
A
H
B
F
E
D
C
G
7
2
10
18
3
4
3
7
8
9
3
10
Select node with minimum
distance
K d
v
p
v
A T 4 H
B T 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H T 3 G
2

21. 4
A
H
B
F
E
D
C
G
2
3
4
3
3
Cost of Minimum Spanning
Tree = S d
v
= 21
K d
v
p
v
A T 4 H
B T 4 C
C T 3D
D T 0 -
E T 2 F
F T 3 C
G T 2 D
H T 3 G
2
Done

22. How many squares can you create in this figure by connecting any 4
dots (the corners of a square must lie upon a grid dot?
TRIANGLES:
How many triangles are located in the image below?

23. There are 11 squares total; 5 small, 4 medium, and 2 large.
27 triangles. There are 16 one-cell triangles, 7 four-cell triangles, 3 nine-cell
triangles, and 1 sixteen-cell triangle.

24. GUIDED READING

26. ASSESSMENT