# 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

,
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.`explore`

### Problem R3.12

The below method takes an undirected graph as a parameter and
returns the vertex with the most neighbors-of-neighbors.
The

class is the same as on Assignment 2;
all instance methods on it take `UndirectedGraph``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

.
(There are 2 `b``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

, there are at most
`b``n` iterations of the loop over

, each
iteration taking `c``O`(1) time. Thus each iteration of
the

loop takes `b``O`(`n`) time.
Over all 2 `m` iterations of the

loop
overall, the time spent is
`b``O`(`m` ⋅ `n`).

The outer loop over

takes just `i``O`(1)
time per iteration, if we neglect the time spent on the

loop. Thus the outer loop takes
`b``O`(`n`) time over all iterations, neglecting
the time on the

loop. The code outside the outer
loop takes `b``O`(1) time.

Thus the total time is
`O`(1 + `n` + `m` ⋅ `n`),
which is
`O`(`m` ⋅ `n`).