CS: Graph Algorithms: BFS and DFS Worksheet

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 3

Explain the main difference between BFS and DFS in terms of how they choose which vertex to visit next.

Accepted Answer

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.

Question 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?

Accepted Answer

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.

Question 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?

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 7

In BFS, why is a queue used instead of a stack?

Accepted Answer

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.

Question 8

In DFS, why can recursion be used to implement the algorithm?

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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?

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

CS: Graph Algorithms: BFS and DFS

More CS Worksheets

More Grade 9-12 Worksheets