ggm (version 0.5)

bfs: Breadth first search

Description

Breadth-first search of a connected undirected graph.

Usage

bfs(gmat, v = 1)

Arguments

gmat

a symmetric matrix with dimnames specifying the edge matrix of the undirected graph

v

an integer, indicating the starting node of the search. Defaults to the first node.

Value

• tree
  the edge matrix of the resulting spanning tree
• branches
  a matrix with two columns, giving the indices of the branches of the spanning tree
• chords
  a matrix with two columns, giving the indices of the chords of the spanning tree

Details

Breadth-first search is a systematic method for exploring a graph. The algorithms is taken from Aho, Hopcroft & Ullman (1983).

References

Aho, A.V., Hopcrtoft, J.E. & Ullman, J.D. (1983). Data structures and algorithms. Reading: Addison-Wesley.

Thulasiraman, K. & Swamy, M.N.S. (1992). Graphs: theory and algorithms. New York: Wiley.

See Also

UG,findPath, cycleMatrix

Examples

## Finding a spanning tree of the butterfly graph
bfs(UG(~ a*b*o + o*u*j))
## Starting from another node
bfs(UG(~ a*b*o + o*u*j), v=3)