22.
Chapter 22 Solutions
Written by Jonathan Sande & Vincent Ngo
Heads up... You’re accessing parts of this content for free, with some sections shown as
text.
Heads up... You’re accessing parts of this content for free, with some sections shown as
text.Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
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