Makes a breadth first Search in a graph.
MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.
MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.
Graph::breadthFirstSearch(G
, <StartVertex = v
>)
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.
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. Rootvertices always have the value 0
(they are
the
roots).
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.
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 invertices!).
This explains also why the next call shows a infinity as
predecessor to l.
 

List containing one vertex. 

Defines a vertex from which to start the breadth first traversal. 
List containing three tables. The first table holds the timestamp of the discovery. The second the distance to the rootvertex. The last table holds the predecessor vertices.