Sorting and search Examples
Depth-first search Example
Use the Depth-first search to explore the following graph:
The starting point is h (arbitrarily).
Below, $\text{a, b, c} \to \text{a}$, means that among the vertices, I picked the vertex $a$, according to the algorithm after examining "marked" and "done".
| 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\}}$ |
Breadth-first search Example
Use the Breadth-first search to explore the following graph:
The starting point is h (arbitrarily).
- h
- $n(\text{h}) = \text{i}$
- $\text{list} = \text{( i )}$
- i
- $n(\text{i}) = \text{j, g}$
- $\text{list} = \text{( j, g )}$
- j
- $n(\text{j}) = \text{e}$
- $\text{list} = \text{( g, e )}$
- g
- $n(\text{j}) = \text{f, d}$
- $\text{list} = \text{( e, f, d )}$
- e
- $n(\text{e}) = \text{b, a}$
- $\text{list} = \text{( f, d, b, a )}$
- f
- $\text{list} = \text{( d, b, b, a )}$
- d
- $n(\text{d}) = \text{k, c}$
- $\text{list} = \text{( b, a, k, c )}$
- b
- $\text{list} = \text{( a, k, c )}$
- a
- $\text{list} = \text{( k, c )}$
- k
- $\text{list} = \text{( c )}$
- c
- $\text{list} = \text{empty}$
We found the vertices: $h-i-j-g-e-f-d-b-a-k-c$.
Eulerian Graph Example
Is the following graph Eulerian? Give an Eulerian path.
All degrees aside from $d(5)$ and $d(7)$ are even, so we may have a semi-Eulerian graph. We can only start at 5 or 7 as $(5,7)$ is a bridge.
- Starting: 7
- We can traverse (7,0), (7,1), or (7,5: bridge)
- Go to 0: (7,0)
- no choice, go to 1: (0,1)
- no choice, go to 7: (1,7)
- no choice, we are destroying the bridge, go to 5: (7,5)
- we can traverse (5,6) or (5,2): (5,2)
- Go to 2: (5,2)
- no choice, go to 6: (2,6)
- no choice, go to 5: (6,5)
So we got the Eulerian path $7-0-1-7-5-2-6-5$ or $(7,0)-(0,1)-(1,7)-(7,5)-(5,2)-(2,6)-(6,5)$.
Hamiltonian Graph Example
Find a Hamiltonian path.
There is the path $(b,a,c,e,d,f)$.
We have $(f,b,a,c,e,d)$ too.
And we have $(a,c,e,d,f,b)$ too.
Did you notice? That's the same path, but we are starting at a different vertex. It seems that we only have one answer.