CSC 225
ALGORITHMS AND DATA STRUCTURES I
ASSIGNMENT 4
1. Let G be a graph whose vertices are integers 1 through 8, and let the adjacent vertices of
each vertex be given by the table below:
vertex Adjacent vertices
1 (2, 3, 4)
2 (1, 3, 4)
3 (1, 2, 4)
4 (1, 2, 3, 6)
5 (6, 7, 8)
6 (4, 5, 7)
7 (5, 6, 8)
8 (5, 7)
Assume that, in a traversal of G, the adjacent vertices of a given vertex are returned in
the same order as they are listed in the above table.
(a) Draw G
(b) Order the vertices as they are visited in a DFS traversal starting at vertex 1.
(c) Order the vertices as they are visited in a BFS traversal starting at vertex 1.
2. For the graph G in Problem 1, draw its adjacency-lists representation and adjacency matrix
representation.
3. Show that every connected graph has a vertex whose removal (including all adjacent edges)
will not disconnect the graph and design a DFS-based algorithm that finds such a vertex.
4. Let F = (V, E) be a forest with n vertices and k connected components. Prove that the
number of edges in F = n − k.
5. Design an algorithm to determine whether a digraph has a unique topological ordering.
1
