Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

21. Chapter 21 Solutions
Written by Jonathan Sande & Vincent Ngo

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