Practice tracing breadth-first search and depth-first search, comparing their behavior, and applying them to common graph problems.
Read each problem carefully. When a graph traversal has choices, visit neighbors in alphabetical order unless the problem says otherwise. Show your work in the space provided.
Exploring breadth-first search and depth-first search on graphs
CS - Grade 9-12
- 1
A graph has vertices A, B, C, D, E, and F. Its edges are A-B, A-C, B-D, B-E, C-F, and E-F. Starting at A, list the order in which BFS visits the vertices. Visit neighbors in alphabetical order.
- 2
Using the same graph with edges A-B, A-C, B-D, B-E, C-F, and E-F, starting at A, list the order in which DFS visits the vertices. Visit neighbors in alphabetical order.
- 3
Explain the main difference between BFS and DFS in terms of how they choose which vertex to visit next.
- 4
A graph is represented by this adjacency list: A: B, C; B: A, D; C: A, D; D: B, C, E; E: D. Starting at A, what is the BFS order if neighbors are visited alphabetically?
- 5
For the adjacency list A: B, C; B: A, D; C: A, D; D: B, C, E; E: D, starting at A, what is the DFS order if neighbors are visited alphabetically?
- 6
A maze can be modeled as a graph where each open square is a vertex and each legal move is an edge. Which algorithm, BFS or DFS, should you use to find the shortest path in an unweighted maze? Explain your choice.
- 7
In BFS, why is a queue used instead of a stack?
- 8
In DFS, why can recursion be used to implement the algorithm?
- 9
Consider a directed graph with edges A to B, A to C, B to D, C to D, and D to E. Starting at A, list the BFS order when outgoing neighbors are visited alphabetically.
- 10
A social network is modeled as an undirected graph. Each person is a vertex, and a friendship is an edge. You want to find all people within two friendship steps of Maya. Which traversal is more useful, BFS or DFS, and why?
- 11
The following graph has two connected components: Component 1 has edges A-B and B-C. Component 2 has edge D-E. Starting BFS at A, which vertices will be visited? Explain what this shows about graph traversal.
- 12
Both BFS and DFS can be used to determine whether a path exists between two vertices in a graph. Describe how you would use either algorithm to test whether there is a path from S to T.