dfs_tree {gor}

Depth-first search tree

Description

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

Usage

dfs_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 last vertex added to the tree. In this way, the tree has many levels and few branches and leaves. When the tree cannot grow further, it backtracks to previously added vertices with neighbors outside the tree, adding them until none is left.

Value

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

Author(s)

Cesar Asensio

See Also

bfs_tree breadth-first search tree; bfs and dfs in the igraph package.

Examples

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