# Documentation

Makes a breadth first Search in a graph.

### Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

## Syntax

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

## Description

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

`Graph::breadthFirstSearch(G, StartVertex = v)` traverses through a graph via breadth first search starting from vertex `v`. The output shows the first time of identification 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 breadthFirstSearch to find out the starting times and predecessors

`Graph::breadthFirstSearch(G)`

Vertex `a` is dicovered first, then vertex b and so on. The right table shows the predecessor of every vertex. The backtracking from a single vertex is therefore really simple. `a` as the first vertex discovered in its component can not be backtracked any further. The distance of each vertex in its component can be read in the middle table. Root-vertices always have the value `0` (they `are` the roots).

### 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 breadth 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::breadthFirstSearch(G2, StartVertex = [a])```

The newly inserted vertex `m` has no predecessor. The predecessor therefore holds 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::breadthFirstSearch(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.

## Parameters

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

## Options

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

## Return Values

List containing three tables. The first table holds the timestamp of the discovery. The second the distance to the root-vertex. The last table holds the predecessor vertices.