6.006 Q2 Bfs/dfs

Front 1

(Spring 2011) The depth of a breadth-first search tree on an undirected graph G = (V, E) from an arbitrary vertex v ∈ V is the diameter of the graph G. (The diameter d of a graph is the smallest d such that every pair of vertices s and t have δ(s, t) ≤ d.)

Back 1

False. An arbitrary vertex could lay closer to the ’center’ of the graph, hence the BFS depth will be underestimating the diameter. For exam- ple, in graph G = (V,E) = ({a,v,b},{(a,v),(v,b)}), a BFS from v will have depth 1 but the graph has diameter 2.

Front 2

(Spring 2011) If a depth-first search on a directed graph G = (V, E) produces exactly one back edge, then it is possible to choose an edge e ∈ E such that the graph G′ = (V, E − {e}) is acyclic.

Back 2

True. Removing the back edge will result in a graph with no back edges, and thus a graph with no cycles (as every graph with at least one cycle has at least one back edge). Notice that a graph can have two cycles but a single back edge, thus removing some edge that disrupts that cycle is insufficient, you have to remove specifically the back edge. For example, in graph G = (V, E) = ({a, b, c}, {(a, b), (b, c), (a, c), (c, a)}), there are two cycles [a, b, c, a] and [a, c, a], but only one back edge (c, a). Removing edge (b, c) disrupts one of the cycles that gave rise to the back edge ([a, b, c, a]), but another cycle remains, [a, c, a].

Front 3

(Spring 2011) If a directed graph G is cyclic but can be made acyclic by removing one edge, then a depth-first search in G will encounter exactly one back edge.

Back 3

False. You can have multiple back edges, yet it can be possible to remove one edge that destroys all cycles. For example, in graph G = (V, E) = ({a, b, c}, {(a, b), (b, c), (b, a), (c, a)}), there are two cycles ([a, b, a] and [a, b, c, a]) and a DFS from a in G returns two back edges ((b, a) and (c, a)), but a single re- moval of edge (a, b) can disrupt both cycles, making the resulting graph acyclic.

Front 4

[Spring 2010] For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic.

Back 4

FALSE. It is true that the absence of back edges with respect to a DFS tree implies that the graph is acyclic. However, the same is not true for a BFS tree. There may be cross edges which go from one branch of the BFS tree to a lower level of another branch of the BFS tree. It is possible to construct a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level).

Front 5

[Spring 2010] The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.

Back 5

TRUE. Since BFS finds paths using the fewest number of edges, the BFS depth of any vertex is at least as small as the DFS depth of the same vertex. Thus, the DFS tree has a greater or equal depth.

Front 6

[Spring 2010] There is no edge in an undirected graph that jumps more than one level of any BFS tree of the graph.

Back 6

TRUE. If such an edge existed, it would provide a shorter path to some node than the path found by BFS (in terms in the number of edges). This cannot happen, as BFS always finds the path with the fewest edges.

Front 7

[Spring 2010] In an unweighted graph where the distance between any two vertices is at most T , any BFS tree has depth at most T , but a DFS tree might have larger depth.

Back 7

TRUE Since all vertices are connected by a path with at most T edges, and since BFS always finds the path with the fewest edges, the BFS tree will have depth at most T . A DFS tree may have depth up to V − 1 (for example, in a complete graph).

Front 8

[Spring 2010] BFS takes O(V + E) time irrespective of whether the graph is presented with an adjacency list or with an adjacency matrix.

Back 8

FALSE. With an adjacency matrix representation, visiting each vertex takes O(V ) time, as we must check all N possible outgoing edges in the adjacency matrix. Thus, BFS will take O(V 2) time using an adjacency matrix.

Front 9

[Spring 2010] An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1.

Back 9

FALSE. If a graph has a Hamiltonian cycle, then it is possible, depending on the ordering of the graph, that DFS will find that cycle and that the DFS tree will have depth V − 1. However, DFS is not guaranteed to find that cycle. (Indeed, finding a Hamiltonian cycle in a graph is NP-complete.) If DFS does not find that cycle, then the depth of the DFS tree will be less than V − 1.

Front 10

[Spring 2009] If a depth-first analysis of a graph contains at least one back edge, any other depth-first analysis of the same graph will also contain at least one back edge.

Back 10

True. This follows from the fact that an analysis contains a back edge if and only if the graph contains a cycle.

Front 11

[Spring 2009] Any DFS forest of an undirected graph contains the same number of trees.

Back 11

True. In an undirected graph, each connected component of the graph will be a single tree in a DFS.

Front 12

[Fall 2009] Given a matrix representation of a graph with V vertices, we can run depth-first search in O(V) time.

Back 12

False

Front 13

[Fall 2009] DFS finds the longest paths from start vertex s to each vertex v in the graph

Back 13

False

Front 14

[Fall 2009] One always obtains the shortest path to each vertex, i.e., one using the minimum number of edges, using breadth-first search.

Back 14

True

Front 15

[Spring 2008] In searching for a shortest path from vertex s to vertex t in a graph, two-way breadth-first search never visits more nodes than a normal one-way breadth-first search.

Back 15

False. Take a graph which looks like many spokes coming out of a center. The starting vertex is on the outside of one of the spokes, and the ending vertex is in the center. Now a one-way BFS will only travel in one spoke, but a 2-way BFS will travel out all of the spokes.

Front 16

[Fall 2008] While running DFS on a directed graph, if from vertex u we visit a finished vertex v, then the edge (u, v) is a cross-edge.

Back 16

False. The edge could be either a cross-edge or a forward edge. Note: The edge cannot be a back edge—a back edge goes to a vertex that has started, but not finished (a “gray vertex”, in CLRS terms).

Front 17

[Fall 2008] A depth-first search of a directed graph always produces the same number of tree edges (i.e. independent of the order in which the vertices are provided and independent of the order of the adjacency lists).

Back 17

False. The DFS forest may contain different numbers of trees (and tree edges) depending on the starting vertex and upon the order in which vertices are searched.
Consider the example below. If the DFS starts at a, then it will visit b next, and (a, b) will become a tree edge. But if the DFS visits b first, then a and b become separate trees in the DFS forest, and (a, b) becomes a cross edge. (Example in test)

Front 18

[Fall 2008] Suppose we do a DFS on a directed graph G. If we remove all of the back edges found, the resulting graph is now acyclic.

Back 18

True. If DFS finds no back edges, then the graph is acyclic. Removing any back edges found doesn’t change the traversal order of DFS, so running DFS again on the modified graph would produce no back edges.

Front 19

[Fall 2008] Both DFS and BFS require Ω(V) storage for their operation. (That is, for working storage, above and beyond the storage needed to represent the input.)

Back 19

True. Each needs to keep track of the vertices that have already been visited.

Front 20

[Fall 2008] Dynamic programming is more closely related to BFS than it is to DFS.

Back 20

False. DFS is more closely related. The top-down approach to dynamic programming is effectively performing DFS on the subproblem dependence graph. The bottom-up approach means solving subproblems in the order of a reverse topological sort, which is also related to DFS.