22. Chapter 22 Solutions

Written by Jonathan Sande

Solution to Challenge 1

The maximum number of items ever in the queue is 3. You can observe this by adding print statements after every enqueue and dequeue in breadthFirstSearch.

Solution to Challenge 2

You already know how to implement the breadth-first search algorithm iteratively. Here’s how you would implement it recursively.

Create an extension on Graph:

extension RecursiveBfs<E> on Graph<E> {

}

Then add a recursive helper method to it:

void _bfs(
  QueueStack<Vertex<E>> queue,
  Set<Vertex<E>> enqueued,
  List<Vertex<E>> visited,
) {
  final vertex = queue.dequeue();
  // 1
  if (vertex == null) return;
  // 2
  visited.add(vertex);
  final neighborEdges = edges(vertex);
  // 3
  for (final edge in neighborEdges) {
    if (!enqueued.contains(edge.destination)) {
      queue.enqueue(edge.destination);
      enqueued.add(edge.destination);
    }
  }
  // 4
  _bfs(queue, enqueued, visited);
}

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

1. This is the base case. The recursion stops when the queue is empty.
2. Mark the vertex as visited.
3. For every edge of the current vertex, check if the adjacent vertices have been visited before inserting them into the queue.
4. Recursively call this function until the queue is empty.

Now add the public bfs method above _bfs:

List<Vertex<E>> bfs(Vertex<E> source) {
  final queue = QueueStack<Vertex<E>>();
  final Set<Vertex<E>> enqueued = {};
  List<Vertex<E>> visited = [];

  queue.enqueue(source);
  enqueued.add(source);

  _bfs(queue, enqueued, visited);
  return visited;
}

This method is much the same as the implementation you wrote earlier in the chapter. The difference now is that you call the recursive helper function rather than using a while loop.

Test it out using the same graph as the one in the chapter text:

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

Run that, and you should again see A to H printed line by line.

The overall time complexity for this breadth-first search implementation is also O(V + E).

Solution to Challenge 3

A graph is said to be disconnected if no path exists between two nodes.

Create an extension on Graph like so:

extension Connected<E> on Graph<E> {
  bool isConnected() {
    // 1
    if (vertices.isEmpty) return true;
    // 2
    final visited = breadthFirstSearch(vertices.first);
    // 3
    for (final vertex in vertices) {
      if (!visited.contains(vertex)) {
        return false;
      }
    }
    return true;
  }
}

The commented numbers refer to the following points:

1. If there are no vertices, treat the graph as connected.
2. Perform a breadth-first search starting from the first vertex. This process will return all the visited nodes.
3. Go through every vertex in the graph and check if it has been visited before.

The graph is disconnected if a vertex is missing in the visited set.