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

23. Chapter 23 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

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

extension RecursiveDfs<E> on Graph<E> {

}
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);
    }
  }
}
List<Vertex<E>> dfs(Vertex<E> start) {
  List<Vertex<E>> visited = [];
  Set<Vertex<E>> pushed = {};
  _dfs(start, visited, pushed);
  return visited;
}
final vertices = graph.dfs(a);
vertices.forEach(print);
A
B
E
F
G
C
H
D
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