`bfsearch`

Breadth-first search: nodes in order of discovery by distance in edges.

Category: Mathematics > Graph and Network Algorithms

Syntax

v = bfsearch(G, s)

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

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

Returns the edges that lead to newly discovered nodes, as rows [source target].

Description

The search visits s, then all its neighbors, then all their unvisited neighbors, and so on, one layer at a time. Within a layer, neighbors are taken in index order. Nodes that cannot be reached from s are not listed.

The layers give the minimum number of edges from s to each node, which makes breadth-first search the tool for unweighted shortest paths. For weighted ones use shortestpath.

Input arguments

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

Output arguments

v: Column vector of node indices, starting with s.
E: Matrix with two columns for the 'edgetonew' form.

Example

Order and tree edges

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

Output

ans = 1×5

     1     2     3     4     5
ans = 4×2

     1     2
     1     3
     2     4
     4     5

Notes

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

bfsearch