594
Graph Algorithms
For Exercises 15 and 16, use Floyd’s algorithm to find the distances for all the shortest paths. Show the successive
values of the a matrix for each pass through the outer loop.
15. Figure 7.10
16. Graph for Exercises 1–4
For Exercises 17–20, use Prim’s algorithm to find a minimal spanning tree for the graph in the specified figure.
17. Graph for Exercises 1–4
algoRitHm kruskal’s algorithm
Kruskal (n × n matrix a; collection of arcs T )
//Finds a minimal spanning tree; T is initially empty;
//at termination, T = minimal spanning tree
order arcs in G by increasing distance
repeat
if next arc in order does not complete a cycle then
add that arc into T
end if
until T is connected and contains all nodes of G
end Kruskal
18.
19.
20.
Kruskal’s algorithm is another algorithm for finding a minimal spanning tree in a connected graph. Whereas
Prim’s algorithm “grows” the tree from an arbitrary starting point by attaching adjacent short arcs, Kruskal’s
algorithm adds arcs in order by increasing distance wherever they may be in the graph. Ties are resolved
arbitrarily. The only restriction is that an arc is not added if adding it would create a cycle. The algorithm
terminates when all nodes have been incorporated into a connected structure. A (very informal) pseudocode
description follows: