22 Chapter 22 Solutions

Solution to Challenge 1

• Path from A to F: Use depth-first because the path you’re looking for is deeper in the graph.
• Path from A to G: Use breadth-first because the path you’re looking for is near the root.

Solution to Challenge 2

In this chapter, you learned how to implement a depth-first search iteratively. Here’s how you would implement it recursively.

Create an extension on Graph:

extension RecursiveDfs<E> on Graph<E> {

}

Then add a recursive helper method to it:

void _dfs(
  Vertex<E> source,
  List<Vertex<E>> visited,
  Set<Vertex<E>> pushed,
) {
  // 1
  pushed.add(source);
  visited.add(source);
  // 2
  final neighbors = edges(source);
  for (final edge in neighbors) {
    // 3
    if (!pushed.contains(edge.destination)) {
      _dfs(edge.destination, visited, pushed);
    }
  }
}

You’ll use this method soon. Here’s what it does:

1. Mark the source vertex as visited.
2. Visit every neighboring edge.
3. As long as the adjacent vertex has not been visited yet, continue to dive deeper down the branch recursively.

Now add the public dfs method above _dfs:

List<Vertex<E>> dfs(Vertex<E> start) {
  List<Vertex<E>> visited = [];
  Set<Vertex<E>> pushed = {};
  _dfs(start, visited, pushed);
  return visited;
}

This method initializes visited and pushed and then starts the recursion process. Unlike the iterative solution you wrote earlier, there’s no stack here. That’s because recursion itself implicitly uses a stack.

Grab the same graph as the one you used in the chapter text. Then add the following:

final vertices = graph.dfs(a);
vertices.forEach(print);

Run that and you should see the same result as the iterative solution:

A
B
E
F
G
C
H
D