Review 3: Graphs & DFS: Questions

R3.1.

Define what an adjacency matrix representation is for an undirected, unweighted graph.

R3.2.

For the below binary tree, give its preorder and postorder traversals.

R3.3.

For the below binary tree, give its preorder and postorder traversals.

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?

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?

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?

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.

R3.8.

What is a dag?

R3.9.

Give a valid topological sort of the below dag.

R3.10.

How many valid topological sorts are there for the below dag? Justify your answer without resorting to listing the orderings.

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.

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 <VV countNeighborsOfNeighbors(UndirectedGraph<Vg) {
    V bestVertex = null;
    int bestCount = -1;
    for(int i = 0i < g.getVertexCount(); i++) {
        V a = g.getVertex(i);
        HashSet<Vneighbneighb = 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;
}

Review 3: Graphs & DFS: Solutions

R3.1.

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 (ij) is 1 if an edge connects vertices i and j in the graph.

R3.2.
preorder:a b d e c
postorder:d e b c a
R3.3.
preorder:a b d e h c f i g
postorder:d h e b i f g c a
R3.4.
prepost
A011
B23
C110
D56
E78
F49
R3.5.
prepost
a23
b110
c45
d69
e017
f78
g1114
h1516
i1213
R3.6.

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.)

R3.7.

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.

R3.8.

A dag is a directed acyclic graph. That is, it is a directed graph that contains no cycles.

R3.9.

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.

R3.10.

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.

R3.11.

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.

R3.12.

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).