Review 3: Graphs & DFS
![](/cs/img/print.png)
R3: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
Problem R3.1
Define what an adjacency matrix representation is for an undirected, unweighted graph.
The adjacency matrix is an n × n matrix of 0's and 1's, where n is the number of vertices in the graph. Matrix entry (i, j) is 1 if an edge connects vertices i and j in the graph.
Problem R3.2
For the below binary tree, give its preorder and postorder traversals.
![](t2.png)
preorder: | a b d e c |
postorder: | d e b c a |
Problem R3.3
For the below binary tree, give its preorder and postorder traversals.
![](t1.png)
preorder: | a b d e h c f i g |
postorder: | d h e b i f g c a |
Problem R3.4
For the below graph, suppose we start a depth-first search from A and use alphabetical order to determine the order in which vertices are explored. What are pre and post numbers for each vertex of the graph?
![](g1.png)
pre | post | |
A | 0 | 11 |
B | 2 | 3 |
C | 1 | 10 |
D | 5 | 6 |
E | 7 | 8 |
F | 4 | 9 |
Problem R3.5
For the below graph, suppose we start a depth-first search from A and use alphabetical order to determine the order in which vertices are explored. What are pre and post numbers for each vertex of the graph?
![](dag4.png)
pre | post | |
a | 2 | 3 |
b | 1 | 10 |
c | 4 | 5 |
d | 6 | 9 |
e | 0 | 17 |
f | 7 | 8 |
g | 11 | 14 |
h | 15 | 16 |
i | 12 | 13 |
Problem R3.6
Suppose we know we have completed a depth-first search of a graph and we've identified pre and post numbers for each vertex. We know u's pre and post numbers are 6 and 9, and we know v's numbers are 2 and 4. What can we conclude about the relationship between u and v in the depth-first search tree?
Since neither interval [6,9] and [2,4] is contained in the other, one cannot be an ancestor of the other. In fact, since there's just one number 5 between v's post number and u's pre number, it must be that v's parent in the tree must be a sibling of u. (If you prefer, u must be v's aunt or uncle.)
Problem R3.7
We saw that in performing a depth-first search on a directed graph, each edge of the graph will fall into one of four categories. Name and describe each of these categories.
A tree edge is one that is traversed in the course of performing the recursion.
A back edge is one that is ignored because its destination is an ancestor of the source vertex.
A cross edge is one that is ignored because its destination was visited prior to visiting the source vertex, but the destination is not an ancestor of the source vertex.
A forward edge is one that is ignored because its destination was previously visited in the course of visiting the source vertex's other neighbors.
Problem R3.8
What is a dag?
A dag is a directed acyclic graph. That is, it is a directed graph that contains no cycles.
Problem R3.9
Give a valid topological sort of the below dag.
![](dag1.png)
Any combination of the six letters is OK, as long as CFED appears as a subsequence and B appears before both A and E. One solution is CBAFED.
Problem R3.10
How many valid topological sorts are there for the below dag? Justify your answer without resorting to listing the orderings.
![](dag3.png)
There are 18. In each ordering, A, B, E, and F must precede C, with A before B and E before F. Either A will come first or E will come first. If A comes first, then B must be either before E, between E and F, or after F. If E comes first, then F must be either before A, between A and B, or after B. Thus, there are 6 ways to order these four vertices; and after those four vertices will be C.
We must also place D, G, and H after C. G must precede H, but D might come before G, between G and H, or after H, for a total of three configurations for each of the six possible orderings of A/B/E/F. Thus the total number of orderings is 3 ⋅ 6 = 18.
Problem R3.11
Suppose we have a dag represented using an adjacency list, and let m represent the number of edges in the dag. Describe an algorithm that determines a valid topological sort of the dag in O(m) time.
Create an empty linked list, and then perform a depth-first search on
the dag. At the end of the recursive function explore
,
add the explored node at the front of the linked list. Following
completion of the depth-first search, the linked list will
contain the vertices in topological order.
Problem R3.12
The below method takes an undirected graph as a parameter and
returns the vertex with the most neighbors-of-neighbors.
The UndirectedGraph
class is the same as on Assignment 2;
all instance methods on it take O(1) time.
Using m to represent the number of edges in the graph and n to represent the number of vertices, what is the running time of the method? Use big-O notation, giving the tightest and simplest bound you can, and justify your answer.
public static <V> V countNeighborsOfNeighbors(UndirectedGraph<V> g) {
V bestVertex = null;
int bestCount = -1;
for(int i = 0; i < g.getVertexCount(); i++) {
V a = g.getVertex(i);
HashSet<V> neighbneighb = new HashSet<V>();
for(V b : g.getNeighbors(a)) {
for(V c : g.getNeighbors(b)) neighbneighb.add(c);
}
if(neighbneighb.size() > bestCount) {
bestVertex = a;
bestCount = neighbneighb.size();
}
}
return bestVertex;
}
O(m ⋅ n).
There are n iterations of the outer loop,
and over all iterations of the outer loop, there are
2 m iterations of the inner loop over b
.
(There are 2 m iterations because if I go through each
vertex and check each edge around it, then I'll end up checking
each edge once for each of its two endpoints.)
For each iteration of the loop over b
, there are at most
n iterations of the loop over c
, each
iteration taking O(1) time. Thus each iteration of
the b
loop takes O(n) time.
Over all 2 m iterations of the b
loop
overall, the time spent is
O(m ⋅ n).
The outer loop over i
takes just O(1)
time per iteration, if we neglect the time spent on the
b
loop. Thus the outer loop takes
O(n) time over all iterations, neglecting
the time on the b
loop. The code outside the outer
loop takes O(1) time.
Thus the total time is O(1 + n + m ⋅ n), which is O(m ⋅ n).