Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!
Get Started for Free

DFS

Depth First Search


Description

This function implements algorithm 4.2.1 of Gross and Yellen. The input is a graph and a node to start from. It returns a standard vertex labeling of graph. This is a vector with elements corresponding to the nodes of graph and with values that correspond to point in the depth first search the node is visited.

Usage

DFS(object, node, checkConn=TRUE)

Arguments

object

An instance of the graph class.

node

A character indicating the starting node.

checkConn

A logical indicating whether the connectivity of the graph should be checked.

Details

This function implements algorithm 4.2.1 of Gross and Yellen. Specific details are given there.

It requires that the graph be connected. By default, this is checked, but since the checking can be expensive it is optional.

A faster and mostly likely better implementation of depth first searching is given by dfs in the RBGL package.

Value

A vector with names given by the nodes of graph whose values are 0 to one less than the number of nodes. These indices indicate the point at which the node will be visited.

Author(s)

R. Gentleman

References

Graph Theory and its Applications, J. Gross and J. Yellen.

See Also

Examples

RNGkind("Mersenne-Twister")
  set.seed(123)
  g1 <- randomGraph(letters[1:10], 1:4, p=.3)
  RNGkind()
  DFS(g1, "a")

graph

graph: A package to handle graph data structures

v1.68.0
Artistic-2.0
Authors
R. Gentleman, Elizabeth Whalen, W. Huber, S. Falcon
Initial release

We don't support your browser anymore

Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.