bfs_tree: Breadth-first search tree

In gor: Algorithms for the Subject Graphs and Network Optimization

Breadth-first search tree

Description

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

Usage

bfs_tree(g, r)

Arguments

g	Graph
r	Root: Starting vertex growing the tree.

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.

Value

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

Author(s)

Cesar Asensio

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))

gor documentation built on May 4, 2023, 1:06 a.m.