gor (version 1.0)

bfs_tree: Breadth-first search tree

Description

Computation of the breadth-first tree search in an undirected graph.

Usage

bfs_tree(g, r)

Value

A directed spanning subgraph of g containing the edges of the BFS tree.

Arguments

g

Graph

r

Root: Starting vertex growing the tree.

Author

Cesar Asensio

Details

Starting from a root vertex, the tree is grown by adding neighbors of the first vertex added to the tree until no more neighbors are left; then it passes to another vertex with neighbors outside the tree. In this way, the tree has few levels and many branches and leaves.

Examples

g <- make_graph("Frucht")
T <- bfs_tree(g, 2)  # Root at v = 2
z <- layout_with_gem(g)
plot(g, layout = z, main = "Breadth-first search tree")
plot(T, layout = z, add = TRUE, edge.color = "cyan4", edge.width = 2)
plot(T, layout = layout_as_tree(T))