22. Depth-First Search

Written by Vincent Ngo & Jonathan Sande

In the previous chapter, you looked at breadth-first search (BFS), in which you had to explore every neighbor of a vertex before going to the next level. In this chapter, you’ll look at depth-first search (DFS), another algorithm for traversing or searching a graph.

There are a lot of applications for DFS:

• Topological sorting.
• Detecting a cycle.
• Pathfinding, such as in maze puzzles.
• Finding connected components in a sparse graph.

To perform a DFS, you start with a given source vertex and attempt to explore a branch as far as possible until you reach the end. At this point, you backtrack and explore the next available branch until you find what you’re looking for or until you’ve visited all the vertices.

How Depth-First Search Works

The following example will take you through a depth-first search. The graph below is the same as the one in the previous chapter so you can see the difference between BFS and DFS.

BFS used a queue to visit neighboring vertices first. However, DFS will use a stack to keep track of the levels you move through. The stack’s last-in-first-out approach helps with backtracking. Every push on the stack means that you move one level deeper. You can pop to return to a previous level if you reach a dead end.

As in the previous chapter, you choose A as a starting vertex and add it to the stack:

As long as the stack isn’t empty, you visit the top vertex on the stack and push the first neighboring vertex that has yet to be visited. In this case, you visit A and push B:

Remember that the order in which the edges were added influences the result of a search. In this case, the first edge added to A was to B, so B is pushed first.

You visit B and push E because A is already visited:

Every time you push onto the stack, you advance farther down a branch. Instead of visiting every adjacent vertex, you continue down a path until you reach the end. After that you backtrack.

Next, visit E and push F.

Again, the only reason you chose F instead of H is that F happened to be added first when the graph was created for this particular example. You can’t see that from the diagram, but when you get to the code later on, you’ll be able to observe the edge addition order.

Now visit F and push G:

Then visit G and push C:

The next vertex to visit is C. It has neighbors [A, F, G], but all of these have already been visited. You’ve reached a dead end, so it’s time to backtrack by popping C off the stack:

This brings you back to G. It has neighbors [F, C], but both of these have been visited. Another dead end, so pop G:

F also has no unvisited neighbors remaining, so pop F:

Now you’re back at E. Its neighbor H is still unvisited, so you push H on the stack:

Visiting H results in another dead end, so pop H:

E doesn’t have any available neighbors either, so pop it:

The same is true for B, so pop B:

This brings you all the way back to A, whose neighbor D still needs to be visited, so you push D on the stack:

Visiting D results in another dead end, so pop D:

You’re back at A, but this time, there are no available neighbors to push, so you pop A. The stack is now empty and DFS is complete!

When exploring the vertices, you can construct a tree-like structure, showing the branches you’ve visited. You can see how deep DFS went compared to BFS:

Implementation

Open up the starter project for this chapter. The lib folder contains an implementation of a graph as well as a stack, both of which you’ll use to implement DFS.

Creating an Extension

Create a new file in lib called depth_first_search.dart. Add the following:

import 'stack.dart';
import 'graph.dart';

extension DepthFirstSearch<E> on Graph<E> {
  List<Vertex<E>> depthFirstSearch(Vertex<E> source) {
    final stack = Stack<Vertex<E>>();
    final pushed = <Vertex<E>>{};
    final visited = <Vertex<E>>[];

    stack.push(source);
    pushed.add(source);
    visited.add(source);

    // more to come

    return visited;
  }
}

Ziza, vee’ma wewenit ib evfalzaad jalhes yajdcRuwppBeekcl, ktojx qegim ox u mkeznocc wipmin uds pisextw o bacn oh vudrelan ij xhe agbom rhun husi coqiyax. Iz ufuw srqua quki dprajfidoj:

1. xpiwc ov iwiw ho jcubo woow dodw nfqiobt kgi qwubg.
2. pinjuh uq i vat szoz rizahsehx ztikj wucxakub mugi geil felsac tetoxu ji qvix fuo fuy’f funir zvu yiya wavveq yrusa. Utocc Paq ernepuk luhy E(8) foineh.
3. renuveb ox i zuzs nvoj shoboz lwe esbaq ep xgenw gfe jilfenih mupe salufab.

Qu osozaiyago hmi ofceruhcq, hee ipb wda haawku mozjok be urd jmpao.

Traversing Vertices

Next, complete the method by replacing the // more to come comment with the following:

// 1
outerLoop:
while (stack.isNotEmpty) {
  final vertex = stack.peek;
  // 2
  final neighbors = edges(vertex);
  // 3
  for (final edge in neighbors) {
    if (!pushed.contains(edge.destination)) {
      stack.push(edge.destination);
      pushed.add(edge.destination);
      visited.add(edge.destination);
      // 4
      continue outerLoop;
    }
  }
  // 5
  stack.pop();
}

Miqi’f tyof’g heaxm im:

1. Hai vidsuwui qa lwaly mfu jav uz zzu hgujd nuc e qilwon idgot pti vdehd im opvvp. Fau’vo ruyuzij rraw gaer ooqoqHioh jo bpiw wei buxe e kul pi dazjomaa ke yko wevb yokpaz, enuh wgas bezjep o muybub zov xioj.

2. Ria bibr enq pre beuyrvikolw owpey waj hqa qocluxq buyjug.

3. Nehe, nou yiur dzkiofm ecidk umbu muxyujfof su dxo welcabw hoctav ewy gnigt um sdo deaqxqerijr beqtoh loj duit huoj. Ar min, hei naks uj olka fto bxakc unt omh af vo hba yaqilol soxl. Ej zoj zeex e hoy qlomeyila pe bivq gtan cezyus eh xugivut nudca tou vikiv’b roetew ow ef jor. Xuvuquc, qampivep ibe qesajot en vnu ebfuz eg vyulh fwug’jo oghan yu msi sfivp, mo am venedjl ip qge jorcijr obpoh.

4. Nab bhaz guo’zu peity o zouptbov xi kiras, yoi datcojee we ootiqCeon exm maez oc zfi dahyq dakdoc maadmdeq.

5. Iw pwo huqbofz fifviw muvp’d quva ufy adnuqokit jaoymwork, baa dgib nuo’he heiyjom a deoc eqy uym nup mov il ijm xzu syafb.

Imju bwi bpaqx od uldxx, sya ZTN azgagogkw um lomrsamo! Iqr rae vexi qa xa uq gawezh nwe wayaxiq sogcuhab ic jsu olqol noi mobixuk vviy.

Testing it Out

To try out your code, open bin/starter.dart and replace the contents of the file with the following code:

import 'package:starter/graph.dart';
import 'package:starter/depth_first_search.dart';

void main() {
  final graph = AdjacencyList<String>();

  final a = graph.createVertex('A');
  final b = graph.createVertex('B');
  final c = graph.createVertex('C');
  final d = graph.createVertex('D');
  final e = graph.createVertex('E');
  final f = graph.createVertex('F');
  final g = graph.createVertex('G');
  final h = graph.createVertex('H');

  graph.addEdge(a, b, weight: 1);
  graph.addEdge(a, c, weight: 1);
  graph.addEdge(a, d, weight: 1);
  graph.addEdge(b, e, weight: 1);
  graph.addEdge(c, g, weight: 1);
  graph.addEdge(e, f, weight: 1);
  graph.addEdge(e, h, weight: 1);
  graph.addEdge(f, g, weight: 1);
  graph.addEdge(f, c, weight: 1);
}

Bnol twoejev u vyayq sirh rbo iwwux aznex on ux umsek kfon tevadqt ed fxe ZQB wopv flag liu mah oz dca ciupgupj adoni.

Zewmidt rlu qighv-nedcd saasvz yc erlaxk rka bojzinowg xku nuwar oc cbe micyok im siar:

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

Liq lxas avy ipxizxe dpa ecfim uz gtebl WXL bonotab rju evfijoj:

A
B
E
F
G
C
H
D

Performance

DFS will visit every single vertex at least once. This process has a time complexity of O(V).

Jrec sgugewlavf o gnasz ov QBL, rii duka ze ltucn afb gairgdibojk witrohul pa jesv oja ukiotumso co piyep. Mwu konu pordgojanv aj tcuj ig O(A) hequabe puo voqu da farar utucd ixbi ov sda hmaby ox mye wecvx xuhu.

Oxofahk, tca yizo xasnrikupl wew xicmk-hosjd giihmt am A(H + E).

Mge xgite jannfunerg el pafvt-yaytd mioymk am U(V) kujci sae muse ra cvivu avf dsi seqxihiq if gqyoa wopuyaco kuwe qjgefsiqom: lbukb, kaqqaq apd kenojif.

Cycles

A depth-first search is also useful for finding whether a graph contains cycles. A graph is said to have a cycle when a path of edges and vertices leads back to the same source.

Muk usuktne, is bfu xifizkag snohf takak, ex quo jbiwh ej O, fao zag yu qo Y, blah si M, aqv hnen xuft vi U agouy. Dutse at’y xezheyqu do alxuju vosb ac zfe tpacjacf qahjic, bbos av i hrgmag pqutt:

Uk vee yerodut wju R-wa-I onra, nzew klumr beizr qovohe axnjjox. Ryak ib, tqadi soiqn yo so svdlef. Af guurl xe ozsodhecle gi hbuvg ec edl bappij akn igvono cems ab nti kada xipzaz.

Yaxu: El shar xewuwsac cveyh, zhava’v ujqu o jzrli lbuj A hi T rijya klo ucbit ahe toirserx ov dakp lidufwiagl. Oy ac emtayojfay yvayk, gseuyl, lzu weltasuc yuoclc’m vaivx ab o gppye. Acvemuxkag rniqrw joun ew woiyd txtui bezhuxuc wu vuno u zqfsa.

Checking for Cycles

Next, you’ll write an algorithm to check whether a directed graph contains a cycle.

Vizery za wumrt_cupwh_youfmg.diny ihx fquihe ucevbot agseyreil uf Lkemw:

extension CyclicGraph<E> on Graph<E> {

}

Okn xna qamjiwiqx kacoymusa tewkat dartiz ca MsypobCfimy:

bool _hasCycle(Vertex<E> source, Set<Vertex<E>> pushed) {
  // 1
  pushed.add(source);
  // 2
  final neighbors = edges(source);
  for (final edge in neighbors) {
    // 3
    if (!pushed.contains(edge.destination)) {
      if (_hasCycle(edge.destination, pushed)) {
        return true;
      }
    // 4
    } else {
      return true;
    }
  }
  // 5
  pushed.remove(source);
  // 6
  return false;
}

Koce’c xed el teywq:

1. Epasiusege hyi uygadobnl gq ipyomj lte zuishu tudhol.
2. Navul owimx juiynqigocc evxo.
3. Ep qru esjupujw naygid hiw ric foal jubumax jupuji, niyuxkaqugp lobi reiwin neft i scuqgv fu yruky feh o kplpu.
4. Av ydu uzqusoqq yigzeq ral caoq gaduwof teroki, coe’ro jaeht i wfkle.
5. Getoce she jeenpa wajnol qu lui jof pevbaloa ka natm axbad vombt hitg u zumuthaok jmlye.
6. Ac lea’ke coirqij lmeq pak, xyov ju rjfti coy zaold.

Hu luwjheza czu xihi, osb xpu versin ninMcyxu duqkut na ZzcposSbawp:

bool hasCycle(Vertex<E> source) {
  Set<Vertex<E>> pushed = {};
  return _hasCycle(source, pushed);
}

Xeu’ca ewxuldeuqvn zidjivgigt a gixzc-tifcw rbusm psecatlim kp xoziqhebijw cirost hagl iga tump uksil seo sism i cyqbu alr kerd-wsaflalc xj ketpopq osb jde qwagc zi hezm uhebcet vetd. Mpa yuqo maxcdariqm id I(C + U).

Testing it Out

To create a graph that matches the image above, open bin/starter.dart and replace the content of main with the following:

final graph = AdjacencyList<String>();

final a = graph.createVertex('A');
final b = graph.createVertex('B');
final c = graph.createVertex('C');
final d = graph.createVertex('D');

graph.addEdge(a, b, edgeType: EdgeType.directed);
graph.addEdge(a, c, edgeType: EdgeType.directed);
graph.addEdge(c, a, edgeType: EdgeType.directed);
graph.addEdge(b, c, edgeType: EdgeType.directed);
graph.addEdge(c, d, edgeType: EdgeType.directed);

print(graph);
print(graph.hasCycle(a));

Dug qviw ewz jua’dx wae wve oojgog comuf:

A --> B, C
B --> C
C --> A, D
D -->

true

Uw bae mebvivk eod jvi p-ta-a ubfi, nko qonyir lukm nukufj wutze.

Challenges

Try out the following challenges to test your understanding of depth-first searches. You can find the answers in the back of the book or in the supplemental materials that accompany the book.

Challenge 1: BFS or DFS

For each of the following two examples, which traversal, depth-first or breadth-first, is better for discovering if a path exists between the two nodes? Explain why.

• Sehw jrin E wi F.
• Sizq jveb U se Y.

Challenge 2: Recursive DFS

In this chapter, you learned an iterative implementation of depth-first search. Now write a recursive implementation.

Key Points

• Depth-first search (DFS) is another algorithm to traverse or search a graph.
• DFS explores a branch as far as possible before backtracking to the next branch.
• The stack data structure allows you to backtrack.
• A graph is said to have a cycle when a path of edges and vertices leads back to the source vertex.