GRAPH Course

Depth-first search

Go back

In French it's called Parcours en profondeur. To summarize, you will traverse a path until you can't go further, then come back to a previous branching and do it again until you traversed every branch.

Algorithm

  • randomly pick a starting vertex
  • make it as traversed
  • then
    • randomly pick of a neighbor not traversed and not "done"
    • if you can
      • then mark the vertex as traversed
      • repeat
    • else
      • then mark this vertex as "done"
      • go back to the previously traversed vertex
      • if there is no traversed vertex remaining, then you are done

Complexity: $O(|V|+|E|)$.


Example

Use the Depth-first search on this graph.

Depth-first search

We are starting at h because that's my choice. I will use the syntax $\text{a, b, c} \to \text{a}$ to say that among the available neighbor vertex, I picked $a$.

  • a vertex is available if it's not inside "done"
  • when picking a vertex, it's random among the vertices that are not in Marked

I used a table to make things easier to look at.

Current Next? Marked Done
$\text{h}$ $\text{i} \to \text{i}$ $\text{\{h\}}$ $\text{\{\}}$
$\text{i}$ $\text{h, j, g} \to \text{j}$ $\text{\{h, i\}}$ $\text{\{\}}$
$\text{j}$ $\text{i, e} \to \text{e}$ $\text{\{h, i, j\}}$ $\text{\{\}}$
$\text{e}$ $\text{j, b, a} \to \text{b}$ $\text{\{h, i, j, e\}}$ $\text{\{\}}$
$\text{b}$ $\text{e, a, d, k} \to \text{a}$ $\text{\{h, i, j, e, b\}}$ $\text{\{\}}$
$\text{a}$ $\text{e, b, f} \to \text{f}$ $\text{\{h, i, j, e, b, a\}}$ $\text{\{\}}$
$\text{f}$ $\text{a, g} \to \text{g}$ $\text{\{h, i, j, e, b, a, f\}}$ $\text{\{\}}$
$\text{g}$ $\text{i, f, d} \to \text{d}$ $\text{\{h, i, j, e, b, a, f, g\}}$ $\text{\{\}}$
$\text{d}$ $\text{b, g, c, k} \to \text{c}$ $\text{\{h, i, j, e, b, a, f, g, d\}}$ $\text{\{\}}$
$\text{c}$ $\text{d} \to \text{???}$ $\text{\{h, i, j, e, b, a, f, g, d, c\}}$ $\text{\{\}}$
Notice that $\text{d}$, the only neighbor of $c$, is inside "Marked", meaning that $c$ is a dead end. We mark $c$ as "done" and go back to $d$.
$\text{c}$ $\text{d} \to \text{d}$ $\text{\{h, i, j, e, b, a, f, g, d, c\}}$ $\text{\{c\}}$
$\text{d}$ $\text{b, g, k} \to \text{k}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d\}}$ $\text{\{c\}}$
$\text{k}$ $\text{b, d} \to^{done} \text{d}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k\}}$ $\text{\{c, k\}}$
$\text{d}$ $\text{b, g, k} \to^{done} \text{g}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d\}}$ $\text{\{c, k, d\}}$
$\text{g}$ $\text{i, f} \to^{done} \text{f}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g\}}$ $\text{\{c, k, d, g\}}$
$\text{f}$ $\text{a} \to^{done} \text{a}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g, f\}}$ $\text{\{c, k, d, g, f\}}$
$\text{a}$ $\text{e, b} \to^{done} \text{b}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g, f, a\}}$ $\text{\{c, k, d, g, f, a\}}$
$\text{a}$ $\text{e} \to^{done} \text{e}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g, f, a, b\}}$ $\text{\{c, k, d, g, f, a, b\}}$
$\text{e}$ $\text{j} \to^{done} \text{j}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g, f, a, b, e\}}$ $\text{\{c, k, d, g, f, a, b, e\}}$
$\text{j}$ $\text{i} \to^{done} \text{i}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g, f, a, b, e, i\}}$ $\text{\{c, k, d, g, f, a, b, e, i\}}$
$\text{i}$ $\text{h} \to^{done} \text{h}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g, f, a, b, e, i\}}$ $\text{\{c, k, d, g, f, a, b, e, i\}}$
$\text{h}$ $\text{done}$ $\text{\{h, i, j, e, b, a, f, g, d, c, d, k, d, g, f, a, b, e, i, h\}}$ $\text{\{c, k, d, g, f, a, b, e, i, h\}}$

"Marked" is the algorithm result, as you can see exactly what path we took. But if you want all the vertex we found, then that's the value of "done".