R igraph 手册页

dfs {igraph}

R 文档

深度优先搜索

描述

深度优先搜索是一种遍历图的算法。它从一个根顶点开始，并尝试尽可能快地远离根顶点。

用法

dfs(
  graph,
  root,
  mode = 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(),
  neimode
)

参数

图	输入图。
root	从其开始搜索的单个根顶点。
模式	对于有向图，指定要遵循的边的类型。“out” 遵循传出边，“in” 遵循传入边。“all” 完全忽略边的方向。“total” 是 “all” 的同义词。此参数对于无向图将被忽略。
unreachable	逻辑标量，指示搜索是否应访问从给定根顶点（或多个顶点）无法访问的顶点。如果为 TRUE，则执行其他搜索，直到访问所有顶点。
order	逻辑标量，指示是否返回顶点的 DFS 顺序。
order.out	逻辑标量，指示是否返回基于离开顶点子树的顺序。
father	逻辑标量，指示是否返回顶点的父顶点。
dist	逻辑标量，指示是否返回搜索树中与根的距离。
in.callback	如果不是 NULL，则它必须是回调函数。每当访问一个顶点时，就会调用它。请参阅下面的详细信息。
out.callback	如果不是 NULL，则它必须是回调函数。当算法完成顶点的子树时，就会调用它。请参阅下面的详细信息。
extra	提供给回调函数的附加参数。
rho	评估回调函数的环境。
neimode	此参数从 igraph 1.3.0 开始已弃用；请改用 mode。

详细信息

回调函数必须具有以下参数

图

输入图在此处传递给回调函数。

数据

一个命名的数值向量，包含以下条目：“vid”，刚刚访问的顶点，“dist”，其与搜索树的根的距离。

extra

extra 参数。

回调必须返回 FALSE 以继续搜索，或返回 TRUE 以终止搜索。请参阅下面的示例，了解如何使用回调函数。

值

一个命名的列表，包含以下条目

root	数值标量。用作搜索起点的根顶点。
neimode	字符标量。函数调用的 mode 参数。请注意，对于无向图，这始终为 “all”，与提供的数值无关。
order	数值向量。顶点 ID，按照搜索访问它们的顺序排列。
order.out	数值向量，顶点 ID，按照完成其子树的顺序排列。
father	数值向量。每个顶点的父顶点，即发现它的顶点。
dist	数值向量，对于每个顶点，它与搜索树的根的距离。

请注意，如果相应的参数为 FALSE，即如果未请求它们的计算，则 order、order.out、father 和 dist 可能是 NULL。

作者

Gabor Csardi csardi.gabor@gmail.com

参见

bfs 用于广度优先搜索。

示例

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

---