ggm: bfsearch – R documentation

Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!

bfsearch

Breadth first search

Breadth-first search of a connected undirected graph.

bfsearch(amat, v = 1)

`amat`	a symmetric matrix with dimnames specifying the adjacency matrix of the undirected graph
`v`	an integer, indicating the starting node of the search. Defaults to the first node.

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

`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

Giovanni M. Marchetti

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.

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

Graphical Markov Models with Mixed Graphs

v2.5

GPL-2

Authors

Giovanni M. Marchetti, Mathias Drton, Kayvan Sadeghi

Initial release

2020-02-014