Answer Happy

1. Consider the graph of
a. Find a minimum-cost spanning tree by Prim's algorithm.
b. Find a minimum-cost spanning tree by Kruskal's algorithm.
c. Find a depth-first spanning tree starting at a and at d.
d. Find a breadth-first spanning tree starting at a and at
d.
2. Describe an algorithm to insert and delete edges in the
adjacency list representation for an undirected graph. Remember
that an edge (i, j) appears on the adjacency list for both vertex i
and vertex j.
3. Implement both Prim's algorithm and Kruskal's algorithm.
Compare the running times of your programs on a set of "random"
graphs.
4. Write a program to find all the connected components of a
graph.
5. Consider the following list of integers:
[1,2,3,4,5,6,7,8,9,10]. Show how this list is sorted by the
following algorithms:
• bubble sort
• selection sort
• insertion sort
• shell sort (you decide on the increments)
• merge sort
• quick sort (you decide on the pivot value
2 b 8 2 2 1 3 2 3 f h