Review 3: Graphs & DFS
printable version
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.
| 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.
| 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?
| 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?
| 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.
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.
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).