Problem 1 (6.6 from text)
Show that the program Dijkstra does not work correctly if arc costs can be negative.
Problem 2 (7.1 from text)
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.
Problem 3 (7.2 from text)
Modify the adjacency list representation for an undirected graph so that
the first edge on the adjacency list for a vertex can be deleted in constant time. Write an algorithm to delete the first edge at a vertex using your new representation. Hint. How do you arrange that the two cells representing edge (i, j) can be found quickly from one another?
Problem 4 (7.3 a, b, d from text)
Consider the graph of Fig. 7.20.
Find a minimum-cost spanning tree by Prim's algorithm.
Find a minimum-cost spanning tree by Kruskal's algorithm.
Find a breadth-first spanning tree starting at a and at d.
