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.

Depth-first graph search

`v = dfsearch(G,s)`

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

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

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

applies depth-first search to graph `v`

= dfsearch(`G`

,`s`

)`G`

starting at node `s`

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

`[___] = dfsearch(___,'`

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 depth-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 Depth-First search algorithm begins at the starting node, `s`

, and
inspects the neighbor of `s`

that has the smallest node index. Then for that
neighbor, it inspects the next undiscovered neighbor with the lowest index. This continues
until the search encounters a node whose neighbors have all been visited. At that point, the
search backtracks along the path to the nearest previously discovered node that has an
undiscovered neighbor. This process continues until all nodes that are reachable from the
starting node have been visited.

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

Event startnode(S) Call DFS(S) function DFS(C) Event discovernode(C) 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 Call DFS(N) END END Event finishnode(C) END

`dfsearch`

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?