gor (version 2.0)

dfs_tree: Depth-first search tree

Description

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

Usage

dfs_tree(g, r)

Value

A directed spanning subgraph of g containing the edges of the DFS 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 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.

See Also

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

Examples

library(igraph)
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))