Standard 8: Graph Traversal 2: DFS and BFS
Short description: Construct and execute graph traversal algorithms based on BFS and DFS.
Relevant notes: Topic C: Graph Traversal.
Full description
Execute BFS, DFS, and variants on a graph. Identify search trees that can be produced by running BFS, DFS, both, or neither. Use BFS and/or DFS to solve graph traversal problems.
Example problem
Part a.
Can this search tree arise from running BFS, DFS, both, or neither? Briefly explain how it can arise or why it can't, as applicable.
Part b.
Can this search tree arise from running BFS, DFS, both, or neither? Briefly explain how it can arise or why it can't, as applicable.
Solution
Part a.
This tree can arise from DFS, but not BFS. It arises from DFS by the following calls:
- explore(u) calls explore(v)
- explore(v) calls explore(x)
- explore(x) calls explore(y), which has no neighbors and finishes.
- explore(x) skips v, which is already marked, and finishes.
- explore(v) calls explore(w), which has no unmarked neighbors left and finishes.
- explore(u) has no unmarked neighbors left.
It can't arise from BFS because the start vertex has to be u, because it has an out-edge in the tree and no in-edge. But u would explore its two neighbors before anything else, so it would have the edge (u,w).
Part b.
This tree can arise from BFS, but not DFS. It arises from BFS by the following order:
- u is popped, puts its neighbors v and w in queue in that order.
- v is popped, puts its neighbor x on the queue. It skips w because it is already marked.
- w is popped, skips its neighbor x because it's already marked.
- x is popped, puts its neighbor y on the queue. It skips v because it is already marked.
- y is popped, has no neighbors.
It cannot arise from DFS. The start node would be u because it is the only one with no incoming edges. explore(u) would either call explore(v) first or explore(w) first. If explore(v) first, then it would recursively call explore(w) at some point, so the edge (v,w) would be in the tree instead of (u,w). If explore(w) first, then it would call explore(x) which would call explore(v), so the edge (x,v) would be in the graph and not (u,v). In either case, this graph is not possible.
Rubric
Rubric.
To pass, a solution must follow the course requirements for writing.
To pass, a solution must pass both parts. In each case, a solution must clearly explain how the tree can arise from the applicable search process, and explain how it is impossible for the tree to arise from the applicable search process. Where applicable, it is not enough to give one example of a DFS or BFS run where the tree does not arise; the explanation must show why no run of DFS or BFS (for any ordering of the neighbors) can give the tree.
The numerical rubric for this problem is:
- 4 (Pass, Near-Perfect): correct, clear, and brief but complete explanations.
- 3 (Pass, Proficient): correct, clear. May summarize slightly too briefly how the trees can arise from the applicable search process. May have slightly handwavy explanations of impossibility as long as they correctly capture why the impossibility holds.
- 2 (Fail, Progress): May give an incorrect answer. May give a correct answer, but with incomplete explanation. May include excess unnecessary writing, vague writing, or confusing writing.
- 1 (Fail, Wrong Track): Gives mostly incorrect answers and/or explanations that do not appear to match up to how DFS and BFS work.