Discrete Structures Graphs

Graphs

For the following graph

1. Starting at node a, list the nodes of the graph in depth- first order.

2. Starting at node e, list the nodes of the graph in breadth- first order.

3. Apply Dijkstra's algorithm to the graph starting at node a to compute the shortest distance to each other node in the graph. Show that distance in the node of the

graph.

4. Show the minimum-cost spanning tree that would be generated by Prim's algorithm if you start at node a.

5. Show the minimum-cost spanning tree that would be generated by Kruskal's algorithm.

Please remember to follow the clock rule: when processing the

successors of a given node, start at the one that is at noon or

beyond, and proceed clockwise. Thus, processing the

successors of a would require you to first process d, then c, and then process b; processing the successor of b; would require you to first process a and then process e. "Process" here means "put onto the stack or queue" (or whatever data structure is

being used). Note that the arcs in the graph are directed,

which affects the successors of a node. Thus c is a successor of a, but a is not a successor of c. Such a directed graph is like a map with one-way streets on it.

Showing work: It is to your advantage to show the steps of your

algorithm, because if you mess up one step your entire result

could be wrong, gaining you little credit.