## Documentation Center |

Makes a depth first Search in a graph.

This functionality does not run in MATLAB.

`Graph::depthFirstSearch(``G`, <`StartVertex = v`>)

`Graph::depthFirstSearch` traverses through
a graph via depth first search. The output shows the first time of
identification, the finishing time and the predecessor of each vertex.
If a vertex is a single vertex with no predecessor its predecessor
is *infinity*.

`Graph::depthFirstSearch(G, StartVertex=v)` traverses
through a graph via depth first search starting from vertex `v`.
The output shows the first time of identification, the finishing time
and the predecessor of each vertex. If a vertex is a single vertex
with no predecessor its predecessor is *infinity*.

A typical tree is created and drawn for a better understanding of the algorithm.

G := Graph([a, b, c, d, e, f, g, h, i, j, k, l], [[a, b], [a, c], [b, d], [b, e], [c, f], [c, g], [d, h], [e, i], [e, j], [f, k], [g, l]], Directed): plot( Graph::plotGridGraph(G, VerticesPerLine = [12, 12, 12, 12], VertexOrder = [ None, None, None, None, None, None, a, None, None, None, None, None, None, None, b, None, None, None, None, None, None, c, None, None, None, d, None, None, e, None, None, f, None, None, g, None, h, None, None, i, None, j, None, None, k, None, None, l ] ) )

Now we call `Graph::depthFirstSearch` to find
out the starting times, the finishing times and the predecessors of
each vertex:

Graph::depthFirstSearch(G)

Vertex `a` is dicovered first, then vertex
b and so on. The table in the middle shows the finishing times. `h` for
example has the finishing time of 5, meaning that vertices `a,
b, c, d` and `h` itself were visited before
it was recognized that `h` is a leaf (finishing time
= starting time + 1). The right table shows the predecessor of every
vertex. The backtacking from a single vertex is therefore really simple. `a` as
the first vertex discovered in its component can not be backtracked
any further.

What happens now, if there exist a vertex that has no connection to any other vertex. The upper example is taken and a single vertex is added without changing anything else. Then a depth first search is invoked on the graph:

G := Graph([a, b, c, d, e, f, g, h, i, j, k, l], [[a, b], [a, c], [b, d], [b, e], [c, f], [c, g], [d, h], [e, i], [e, j], [f, k], [g, l]], Directed):

G2 := Graph::addVertices(G, [m]): Graph::depthFirstSearch(G2, StartVertex = [a])

The newly inserted vertex `m` has no predecessor.
The predecessor holds therefore the value *infinity*.

If we start somewhere in the graph without knowing the root of the DAG, the results are of course different:

G := Graph([a, b, c, d, e, f, g, h, i, j, k, l], [[a, b], [a, c], [b, d], [b, e], [c, f], [c, g], [d, h], [e, i], [e, j], [f, k], [g, l]], Directed):

Graph::depthFirstSearch(G, StartVertex = [c])

The predecessor of `c` is `c`,
but if we look at the graph it should be `a`. This
is nevertheless not quite correct. Breadth first search takes the
given vertex and uses this as the root of the graph (no in-vertices!).
This explains also why the next call shows a *infinity* as
predecessor to l:

Graph::depthFirstSearch(G, StartVertex = [l])

Was this topic helpful?