`dfsearch`

Depth-first search: nodes in the order a depth-first traversal discovers them.

Category: Mathematics > Graph and Network Algorithms

Syntax

v = dfsearch(G, s)

Returns the nodes reachable from s in depth-first order.

E = dfsearch(G, s, 'edgetonew')

Returns the edges that lead to newly discovered nodes.

Description

The search follows one path as far as it goes, then backs up to the most recent node that still has an unvisited neighbor and continues from there. Neighbors are tried in index order. Only nodes reachable from s are returned.

Depth-first search underlies topological sorting, cycle detection and the computation of strongly connected components.

Input arguments

G: A graph or digraph.
s: Start node, as index or name.
events: Event name that selects what is reported, such as 'edgetonew'.

Output arguments

v: Column vector of node indices, starting with s.
E: Two-column matrix for the 'edgetonew' form.

Example

Depth-first order

D = digraph([1 1 2 3 4], [2 3 4 4 5]);
dfsearch(D, 1)'
dfsearch(D, 1, 'edgetonew')

Output

ans = 1×5

     1     2     4     5     3
ans = 4×2

     1     2
     2     4
     4     5
     1     3

Notes

MatLivre returns plain node lists for event names such as 'allevents' instead of the event table that MATLAB builds. Use the default and 'edgetonew' forms for portable code.

dfsearch