22.
Chapter 22 Solutions
Written by Jonathan Sande & Vincent Ngo
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
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
Prev chapter
21.
Chapter 21 Solutions
Next chapter
23.
Chapter 23 Solutions