Note: This page has been translated by MathWorks. Please click here

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

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

Breadth-first graph search

`v = bfsearch(G,s)`

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

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

restarts the search if no new nodes are reachable from the discovered nodes. You can use
any of the input 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, `T`

= bfsearch(___,'`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 discovernode(S) NodeList = {S} WHILE NodeList is not empty C = NodeList{1} Remove first element from NodeList FOR node N from successors of node C Event edgetonew(C,N), edgetodiscovered(C,N) or edgetofinished(C,N) (depending on the state of node N) IF event was edgetonew Event discovernode(N) Append N to the end of NodeList END END Event finish(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?