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

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

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

Depth-first graph search

`v = dfsearch(G,s)`

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

`T = dfsearch(___,'Restart',true)`

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
depth-first search reaches all nodes and edges in the graph, even if they are not reachable
from the starting node, `T`

= dfsearch(___,'`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:

function DFS(C) Event discovernode(C) 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 Call DFS(N) END END Event finish(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?