Description
Question 1. Figure 1 shows a directed graph G.
a
b
c
d
e
f
g
Figure 1: A directed graph for use in Question 1 and Question 2.
(i) Give the adjacency-list representation of G. When giving your answer, please order the
vertices alphabetically. [2.5 points]
(ii) Give the adjacency-matrix representation of G. When giving your answer, please order
the vertices alphabetically. [2.5 points]
Question 2. Consider the directed graph G in Fig. 1, and run the breadth-first search on G,
with vertex a as the source vertex. Assume that at each level, the vertices are traversed in
alphabetical order.
(i) Show the d and π values that result from running breadth-first search on the directed
graph G. Note that d is the attribute representing the distance/level for the breadth-first
search, while π is the attribute representing the pointer that points to the previous vertex.
You can write in the form of V ertex(d, π). For example, if x is a vertex such that x.d = 1
and x.π = y, then you can write x(1, y). [3 points]
(ii) Based on your answers from the previous part, find a shortest path from vertex a to vertex
g. Make sure you use the d and π values of the vertices of G. [2 points]
1
Question 3. The incidence matrix of a directed graph G = (V, E) with no self-loops is a
|V | ∗ |E| matrix B whose (i, j)-th entry bi,j is defined by
bi,j =
−1, if the j-th directed edge leaves the i-th vertex;
1, if the j-th directed edge enters the i-th vertex;
0, otherwise.
(1)
Explain what the entries of the matrix product BBT
represent, where BT
is the transpose of
B. Justify your answer with details. [5 points]
Question 4. The pseudocode for one possible implementation of the breadth-first search (BFS)
algorithm is shown on page 29 of slides L06 (“queue + adj list implementation version”). For
this question, we shall refer to this particular pseudocode.
(i) What is the purpose of assigning colors to vertices? [2 points]
(ii) In this pseudocode, three distinct colors WHITE, GRAY, BLACK are used as the possible
attribute values for the color attribute of a vertex. Explain how this pseudocode can be
modified, so that only a single bit is used to store the color attribute value of every vertex.
Justify your answer with details. [3 points]
Question 5. Most graph algorithms that take an adjacency-matrix representation of a directed
graph G = (V, E) as input has time complexity Ω(|V |
2
), but there are some exceptions. A
universal sink is a vertex with in-degree |V | − 1 and out-degree 0. For this question, suppose
that the adjacency matrix A for some directed graph G is provided.
(i) Design an algorithm that takes as its input the adjacency matrix A and an index k, and
returns T RUE or F ALSE, depending on whether the k-th vertex of G is a universal
sink or not, respectively, such that your algorithm runs in O(|V |) time. Please give your
algorithm in pseudocode, and please explain in detail why your pseudocode works, as well
as why your algorithm runs in O(|V |) time. [2.5 points]
(ii) Explain why G can have at most one universal sink. Design an algorithm that takes as
its input the adjacency matrix A, and either returns the character string “There is no
universal sink” if G has no universal sink, or returns the index of the universal sink, if G
has a universal sink. [2.5 points]
2