Analysis of Algorithms : An Active Learning Approach

162 GRAPH ALGORITHMS

6.4.3

1. Find the minimum spanning tree using the Dijkstra-Prim algorithm for the
   following graphs starting at node A. Show all steps.


2. Find the minimum spanning tree using the Kruskal algorithm for the graphs
   in question 1. Show all steps.


3. Do an analysis of the Dijkstra-Prim minimum spanning tree algorithm,
   counting the number of times that an edge is considered for nodes added to
   the fringe, for updating edges to the fringe nodes, or to pick the node to
   move from the fringe to the minimum spanning tree.


4. Prove that if there is one edge with a weight smaller than all of the other
   edges, that edge will be part of every minimum spanning tree.


5. Prove that if a connected graph has edge weights that are all distinct (in
   other words, no two edges have the same weight), there is only one mini-
   mum spanning tree.

■6.4.3 EXERCISES

A B C

F G H

D E

4

11

1

2

2

2

5

4

4

4

4

2

2

2

3

3 3

35

(^366)
a. b. A B
DE
FG
C
A B C
F G H
D E
45
4
1
22
5 24
1
1
4
2
1
3
2
2
3
5
5
(^223)
c. d. A B
DE
G H
C
F
2