Note: This page has been translated by MathWorks. Click here to see

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

Breadth-first graph search

`v = bfsearch(G,s)`

`T = bfsearch(G,s,events)`

`[T,E] = bfsearch(G,s,events)`

`[___] = bfsearch(___,'Restart',true)`

applies breadth-first search to graph
`v`

= bfsearch(`G`

,`s`

)`G`

starting at node `s`

. The result is a vector of
node IDs in order of their discovery.

`[___] = bfsearch(___,'`

restarts the search if no new nodes are reachable from the discovered nodes. You can use
any of the input or output argument combinations in previous syntaxes. This option ensures
that the breadth-first search reaches all nodes and edges in the graph, even if they are
not reachable from the starting node, `Restart`

',true)`s`

.

`dfsearch`

and`bfsearch`

treat undirected graphs the same as directed graphs. An undirected edge between nodes`s`

and`t`

is treated like two directed edges, one from`s`

to`t`

and one from`t`

to`s`

.

The Breadth-First search algorithm begins at the starting node, `s`

, and
inspects all of its neighboring nodes in order of their node index. Then for each of those
neighbors, it visits their unvisited neighbors in order. The algorithm continues until all
nodes that are reachable from the starting node have been visited.

In pseudo-code, the algorithm can be written as:

Event startnode(S) Event discovernode(S) NodeList = {S} WHILE NodeList is not empty C = NodeList{1} Remove first element from NodeList FOR edge E from outgoing edges of node C, connecting to node N Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E) (depending on the state of node N) IF event was edgetonew Event discovernode(N) Append N to the end of NodeList END END Event finishnode(C) END

`bfsearch`

can return flags to describe the different events in the
algorithm, such as when a new node is discovered or when all of the outgoing edges of a node
have been visited. The event flags are listed here.

Event Flag | Event Description |
---|---|

`'discovernode'` |
A new node has been discovered. |

`'finishnode'` |
All outgoing edges from the node have been visited. |

`'startnode'` |
This flag indicates the starting node in the search. |

`'edgetonew'` |
Edge connects to an undiscovered node |

`'edgetodiscovered'` |
Edge connects to a previously discovered node |

`'edgetofinished'` |
Edge connects to a finished node |

For more information, see the input argument description for
`events`

.

In cases where the input graph contains nodes that are unreachable from the starting
node, the `'Restart'`

option provides a way to make the search visit every
node in the graph. In that case, the `'startnode'`

event indicates the
starting node each time the search restarts.

Was this topic helpful?