Traverse graph by following adjacent nodes
[
disc
, pred
, closed
] = graphtraverse(G
, S
)[...] = graphtraverse(
G
, S
, ...'Depth', DepthValue
, ...)[...] = graphtraverse(
G
, S
, ...'Directed', DirectedValue
, ...)[...] = graphtraverse(
G
, S
, ...'Method', MethodValue
, ...)
G  NbyN sparse matrix that represents a directed graph. Nonzero
entries in matrix G indicate the presence
of an edge. 
S  Integer that indicates the source node in graph G . 
DepthValue  Integer that indicates a node in graph G that
specifies the depth of the search. Default is Inf (infinity). 
DirectedValue  Property that indicates whether graph G is
directed or undirected. Enter false for an undirected
graph. This results in the upper triangle of the sparse matrix being
ignored. Default is true . 
MethodValue  String that specifies the algorithm used to traverse the graph.
Choices are:

Tip For introductory information on graph theory functions, see Graph Theory Functions. 
[
traverses graph disc
, pred
, closed
] = graphtraverse(G
, S
)G
starting
from the node indicated by integer S
. G
is
an NbyN sparse matrix that represents a directed graph. Nonzero
entries in matrix G
indicate the presence
of an edge. disc
is a vector of node indices
in the order in which they are discovered. pred
is
a vector of predecessor node indices (listed in the order of the node
indices) of the resulting spanning tree. closed
is
a vector of node indices in the order in which they are closed.
[...] = graphtraverse(
calls G
, S
, ...'PropertyName
', PropertyValue
, ...)graphtraverse
with
optional properties that use property name/property value pairs. You
can specify one or more properties in any order. Each PropertyName
must
be enclosed in single quotes and is case insensitive. These property
name/property value pairs are as follows:
specifies the depth of the search. [...] = graphtraverse(
G
, S
, ...'Depth', DepthValue
, ...)DepthValue
is
an integer indicating a node in graph G
.
Default is Inf
(infinity).
indicates whether the graph
is directed or undirected. Set [...] = graphtraverse(
G
, S
, ...'Directed', DirectedValue
, ...)DirectedValue
to false
for
an undirected graph. This results in the upper triangle of the sparse
matrix being ignored. Default is true
.
lets you specify the algorithm
used to traverse the graph. Choices are:[...] = graphtraverse(
G
, S
, ...'Method', MethodValue
, ...)
'BFS'
— Breadthfirst search.
Time complexity is O(N+E)
, where N
and E
are
number of nodes and edges respectively.
'DFS'
— Default algorithm.
Depthfirst search. Time complexity is O(N+E)
,
where N
and E
are number of
nodes and edges respectively.
Create a directed graph with 10 nodes and 12 edges.
DG = sparse([1 2 3 4 5 5 5 6 7 8 8 9],...
[2 4 1 5 3 6 7 9 8 1 10 2],true,10,10)
DG =
(3,1) 1
(8,1) 1
(1,2) 1
(9,2) 1
(5,3) 1
(2,4) 1
(4,5) 1
(5,6) 1
(5,7) 1
(7,8) 1
(6,9) 1
(8,10) 1
h = view(biograph(DG))
Biograph object with 10 nodes and 12 edges.
Traverse the graph to find the depthfirst search (DFS) discovery order starting at node 4.
order = graphtraverse(DG,4) order = 4 5 3 1 2 6 9 7 8 10
Label the nodes with the DFS discovery order.
for i = 1:10 h.Nodes(order(i)).Label =... sprintf('%s:%d',h.Nodes(order(i)).ID,i); end h.ShowTextInNodes = 'label' dolayout(h)
Traverse the graph to find the breadthfirst search (BFS) discovery order starting at node 4.
order = graphtraverse(DG,4,'Method','BFS') order = 4 5 3 6 7 1 9 8 2 10
Label the nodes with the BFS discovery order.
for i = 1:10 h.Nodes(order(i)).Label =... sprintf('%s:%d',h.Nodes(order(i)).ID,i); end h.ShowTextInNodes = 'label' dolayout(h)
Find and color nodes that are close to (within two edges of) node 4.
node_idxs = graphtraverse(DG,4,'depth',2) node_idxs = 4 5 3 6 7 set(h.nodes(node_idxs),'Color',[1 0 0])
[1] Sedgewick, R., (2002). Algorithms in C++, Part 5 Graph Algorithms (AddisonWesley).
[2] Siek, J.G., Lee, LQ, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).