CS341 -- Sections 103 and 301 -- Homework 4
Due Dates --- Homework will be collected at the start of class
Section 101 -- Thursday, December 3, 1998
Section 201 --Wednesday, December 2, 1998
Homework should be hand-written and on hard-copy.
Late Homework will not be accepted
Each of the following questions refer to the following graph:
- Draw an adjaceny table for the graph (5 points).
- Draw an adjaceny list (Array of lists of indicies) for the graph (5
points)
- Show a Breadth-First Search of the graph, starting at vertex E.
Show the contents of the queue at each step of the BFS.(10 points)
- Show a Depth-First-Search of the graph, starting at vertex C.
Show the contents of the stack at each step of the DFS (10 points)
- Run either Prim's or Kruskal's algorithm to generate a Minimum Spanning Tree(10 points)
Provide a drawing of the graph which clearly indicates your MST (highlight the edges chosen)
For Prim's algorithm, list the edges of the MST in the order chosen.
For Kruskal's algorithm -- show the edges in sorted order, then indicate whether the edges is
selected or rejected. If rejected, indicate the reason.
- Run Dijkstra's algorithm to find the shortest path from E to K (10 points).
Your solution should show all intermmediate values for the calculated shortest distance
and each node's "predecessor". Indicate both the shortest path and it's
total weight