Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

22. Chapter 22 Solutions
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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.

extension RecursiveBfs<E> on Graph<E> {

}
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);
}
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;
}
final vertices = graph.bfs(a);
vertices.forEach(print);

Solution to Challenge 3

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

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;
  }
}
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now