# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English verison of the page.

# `Graph`::`depthFirstSearch`

Makes a depth first Search in a graph.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

## Syntax

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

## Description

`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.

## Examples

### Example 1

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.

### Example 2

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.

### Example 3

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])`

## Parameters

 `G` `Graph` `v` List containing one vertex.

## Options

 `StartVertex` Defines a vertex from which to start the depth first traversal.

## Return Values

List containing three tables. The first table holds the first identification timestamp of each vertex, the second the finishing timestamp and the third the predecessor vertex.