CSC 207 Grinnell College Fall, 2018
 
Algorithms and Object-Oriented Design
 

Graphs, Problem Set 1

Adjacency Matrices and Lists

  1. Walker, pp. 486-489, problems 3a, 4, 7, 8, 22, 23, 26a,b

Traversals

  1. Walker, pp. 486-487, problems 9, 10, 18a,b, 19a,b

  2. Suppose a connected graph has v vertices and e edges. What is the complexity of a breadth-first search?

    1. Assume the queue is implemented with an array, and the graph by an adjacency matrix.

    2. Assume the queue is implemented with a linked list, and the graph with adjacency lists.

created 1 December 2018
refined 2 December 2018 		Valid HTML 4.01! Valid CSS!