CS: Graph Algorithms: BFS and DFS
Exploring breadth-first search and depth-first search on graphs
CS: Graph Algorithms: BFS and DFS
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.
Use a queue and write down the vertices as they are removed from the front.
BFS visits the vertices in this order: A, B, C, D, E, F. BFS starts at A, then visits all neighbors of A before moving to vertices at the next level. - 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.
DFS visits the vertices in this order: A, B, D, E, F, C. DFS goes as deep as possible along one path before backtracking to try another unvisited neighbor. - 3
Explain the main difference between BFS and DFS in terms of how they choose which vertex to visit next.
Think about a queue for BFS and a stack or recursion for DFS.
BFS visits vertices in layers by exploring all neighbors at the current distance before moving farther away. DFS follows one path as far as possible before backtracking to explore other paths. - 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?
The BFS order is A, B, C, D, E. After visiting A, BFS enqueues B and C, then reaches D from B or C, and finally reaches E from D. - 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?
Mark a vertex as visited as soon as you enter it.
The DFS order is A, B, D, C, E. Starting at A, DFS goes to B, then D, then C because C is the first unvisited neighbor of D in alphabetical order, and then it returns to D and visits E. - 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.
Unweighted means every move has the same cost.
BFS should be used because it explores all positions at distance 1, then distance 2, and so on. In an unweighted graph, the first time BFS reaches the goal, it has found a shortest path. - 7
In BFS, why is a queue used instead of a stack?
A queue is used in BFS because it processes vertices in first-in, first-out order. This makes the algorithm finish exploring the current layer before moving to the next layer. - 8
In DFS, why can recursion be used to implement the algorithm?
The call stack keeps track of where the algorithm should return after reaching a dead end.
Recursion can be used for DFS because each recursive call continues exploring from the current vertex before returning to the previous vertex. This matches the idea of going deep first and then backtracking. - 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.
The BFS order is A, B, C, D, E. BFS first visits B and C from A, then visits D from B or C, and finally visits E from D. - 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?
One friendship step means a direct friend. Two friendship steps means a friend of a friend.
BFS is more useful because it explores people by distance from Maya. It can easily find everyone at distance 1 and distance 2 before going farther. - 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.
Starting BFS at A visits A, B, and C only. This shows that a traversal from one starting vertex can only reach vertices in the same connected component. - 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.
You do not need to list every possible path. You only need to see whether T is reachable.
Start BFS or DFS at S and mark each visited vertex. If the algorithm visits T, then a path from S to T exists. If the traversal finishes without visiting T, then no path from S to T exists.