DFS {graph} | R Documentation

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

`boundary`

### Examples

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

[Package graph version 1.58.2 Index]