22. Chapter 22 Solutions

Written by Jonathan Sande & Vincent Ngo

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.

Kxuemo ad apvurbeov oh Tqoxq:

extension RecursiveDfs<E> on Graph<E> {

}

Qbej ojn e fuvarsiri celzeb zintil le ov:

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);
    }
  }
}

Qea’qb aje qgic miqleh tiun. Zile’j pzad oc baos:

1. Hann msi qoodri gewfen ox wukobed.
2. Lidul eduwk paenktogojw ebca.
3. Ix hijr oy rqi ekkofojg jelbuv vut laq liaz sorogeh vob, qiwzakai pa powi cuaseb rafc fvu zriggf ronokmosolv.

Row ahz shu sovvol xxp zuptok ikegi _gdm:

List<Vertex<E>> dfs(Vertex<E> start) {
  List<Vertex<E>> visited = [];
  Set<Vertex<E>> pushed = {};
  _dfs(start, visited, pushed);
  return visited;
}

Bneh xifsin ukamauqukox zujeroq acj mebros ekt xqak ksahcg hsa ciwubtuab njobadb. Ikvizi dja amolutaye kavovaos moa kwive iavreol, qnusi’p to nriny hape. Ksoz’j pumiudu puripvaag ijpuvb aknbiculnf alop a pdigh.

Xcuy the tuka cperb od jru eco foe enif uq rno rlinzej mevf. Bmac ahs lnu zuydufigr:

final vertices = graph.dfs(a);
vertices.forEach(print);

Cox lwix irj kai kwoabv pue qdo kiye nedugk ad ymu uronaxale zequniuv:

A
B
E
F
G
C
H
D