6.8 PROGRAMMING EXERCISES 175
what you have found. If you do this for multiple graphs for each maximum,
your results will be more reliable.
- Generate a complete weighted undirected graph with 50 nodes. Run the
Kruskal minimum spanning tree algorithm. If faced with two edges of the
same weight, randomly choose between them. Generate 10 minimum span-
ning trees for each graph and see how many are unique. Because you make
choices randomly, if there are multiple minimum spanning trees based on
these choices, you should find them. Do this process four times with a max-
imum random edge weight of 10, 25, 50, and 100. Write a report of your
results with an explanation of what you have found. If you do this for mul-
tiple graphs for each maximum, your results will be more reliable.
- Generate a complete weighted undirected graph with 50 nodes. For every
pair of nodes (A and B), check to see if the shortest path generated from A
to B is the same as the shortest path generated from B to A, and note how
many times they are different. Do this process four times with a maximum
random edge weight of 10, 25, 50, and 100. Write a report of your results
with an explanation of what you have found. If you do this for multiple
graphs for each maximum, your results will be more reliable.
- Write a program that will generate a complete weighted undirected graph
and then use the Dijkstra–Prim and Kruskal minimum spanning tree algo-
rithms. You should put in counters to keep track of how many times each
algorithm looks at any edge. In other words, count every time the adjacency
matrix is accessed. Run this for graphs with 10, 25, 50, and 100 nodes, and
then write a report comparing the relative efficiencies of these two algo-
rithms. To get more accurate results, you should generate and test multiple
random graphs of each size.
