# dfs

From igraph v1.0.0
by Gabor Csardi

##### Depth-first search

Depth-first search is an algorithm to traverse a graph. It starts from a root vertex and tries to go quickly as far from as possible.

- Keywords
- graphs

##### Usage

```
dfs(graph, root, neimode = c("out", "in", "all", "total"),
unreachable = TRUE, order = TRUE, order.out = FALSE, father = FALSE,
dist = FALSE, in.callback = NULL, out.callback = NULL, extra = NULL,
rho = parent.frame())
```

##### Arguments

- graph
- The input graph.
- root
- The single root vertex to start the search from.
- neimode
- For directed graphs specifies the type of edges to follow.
out follows outgoing,in incoming edges.all ignores edge directions completely.total is a synonym forall . Th - unreachable
- Logical scalar, whether the search should visit the
vertices that are unreachable from the given root vertex (or vertices). If
`TRUE`

, then additional searches are performed until all vertices are visited. - order
- Logical scalar, whether to return the DFS ordering of the vertices.
- order.out
- Logical scalar, whether to return the ordering based on leaving the subtree of the vertex.
- father
- Logical scalar, whether to return the father of the vertices.
- dist
- Logical scalar, whether to return the distance from the root of the search tree.
- in.callback
- If not
`NULL`

, then it must be callback function. This is called whenever a vertex is visited. See details below. - out.callback
- If not
`NULL`

, then it must be callback function. This is called whenever the subtree of a vertex is completed by the algorithm. See details below. - extra
- Additional argument to supply to the callback function.
- rho
- The environment in which the callback function is evaluated.

##### Details

The callback functions must have the following arguments: [object Object],[object Object],[object Object] See examples below on how to use the callback functions.

##### Value

- A named list with the following entries:
root Numeric scalar. The root vertex that was used as the starting point of the search. neimode Character scalar. The `neimode`

argument of the function call. Note that for undirected graphs this is alwaysall , irrespectively of the supplied value.order Numeric vector. The vertex ids, in the order in which they were visited by the search. order.out Numeric vector, the vertex ids, in the order of the completion of their subtree. father Numeric vector. The father of each vertex, i.e. the vertex it was discovered from. dist Numeric vector, for each vertex its distance from the root of the search tree. - Note that
`order`

,`order.out`

,`father`

, and`dist`

might be`NULL`

if their corresponding argument is`FALSE`

, i.e. if their calculation is not requested.

##### See Also

`bfs`

for breadth-first search.

##### Examples

```
## A graph with two separate trees
dfs(make_tree(10) %du% make_tree(10), root=1, "out",
TRUE, TRUE, TRUE, TRUE)
## How to use a callback
f.in <- function(graph, data, extra) {
cat("in:", paste(collapse=", ", data), "\n")
FALSE
}
f.out <- function(graph, data, extra) {
cat("out:", paste(collapse=", ", data), "\n")
FALSE
}
tmp <- dfs(make_tree(10), root=1, "out",
in.callback=f.in, out.callback=f.out)
## Terminate after the first component, using a callback
f.out <- function(graph, data, extra) {
data['vid'] == 1
}
tmp <- dfs(make_tree(10) %du% make_tree(10), root=1,
out.callback=f.out)
```

*Documentation reproduced from package igraph, version 1.0.0, License: GPL (>= 2)*

### Community examples

Looks like there are no examples yet.