4.
G REEDY A LGORITHMS II
‣ Prim's algorithm demo
Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
Copyright © 2013 Kevin Wayne
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on Sep 8, 2013 6:19 AM
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
7 3 11
1 6 8 12 5 10 9
4 13 2
2
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
3 11
3
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
4
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
7 11
8 12 5
5
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
6
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
7 11
8 10
13 2
7
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
8
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
7 11
10
8 9
13
9
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
10
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
11
10
1 6 8 9
13
11
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
12
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
11
10
6 8 9
4 13
13
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
14
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
11
10
9
15
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
16
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
17
Prim's algorithm demo
Initialize S = any node.
Repeat n – 1 times:
Add to tree the min weight edge with one endpoint in S.
Add new node to S.
7 3
1 5 9
4 2
18
4. G REEDY A LGORITHMS II
‣ Kruskal's algorithm demo
Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
Copyright © 2013 Kevin Wayne
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on Sep 8, 2013 6:19 AM
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
9 2
1 5 7 6 4
3 8
2
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
3
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
4
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
5
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
6
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
7
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
8
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
9
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
10
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
11
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
12
Kruskal's algorithm demo
Consider edges in ascending order of weight:
Add to tree unless it would create a cycle.
1 7 4
13
