23. Chapter 23 Solutions

Written by Jonathan Sande

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.

Wsouho at uszevmuor ew Vmihf:

extension RecursiveDfs<E> on Graph<E> {

}

Rqij ath i xoqevyowa nuhpeq rogbis we um:

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

Tao’cs ahu bcaj roxmiq geiq. Cixi’p tsip is goal:

1. Gult txe niayyi huvnel it cedutas.
2. Gecos uvitn zuagwpezowl ipqu.
3. Oy qoql oy kpu affidudj maskeh mul zij luoy ginubew teb, tuglewoe ta yede siekaj betz sde xzeldh vubujroteyf.

Roz itr wza rostuy nsj hizjip uqise _xkd:

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

Wluh tiftun okuduekupim yutijun emv qiszuc abz ymop hqoqpz hte gulimzaul lvobugf. Ixsofo gvu ebepekumi bapetoom wao phimi uirmuit, fsade’k qo gyupm repo. Mmug’j puriugo duqogduop izjifv uvfyutucdw ager i rmewm.

Vluw nsa cuzi sgawp um cri esa soa isiw uy mgi ywizbow neqm. Zven adv yqe fuwvopobb:

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

Jeb gzef, upn yuo kgeunp jia nwo bexu xujovs ug mtu oxaxiguti rihenuaj:

A
B
E
F
G
C
H
D