跳到内容

深度优先搜索

来源：R/structural-properties.R
dfs.Rd

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

用法

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

参数

graph

输入图。

root

从中开始搜索的单个根顶点。

mode

对于有向图，指定要遵循的边的类型。“out”遵循出边，“in”遵循入边。“all”完全忽略边方向。“total”是“all”的同义词。 此参数对于无向图将被忽略。

...

这些点用于未来的扩展，并且必须为空。

unreachable

逻辑标量，指示搜索是否应访问从给定根顶点（或多个顶点）无法访问的顶点。 如果为 TRUE，则执行额外的搜索，直到访问所有顶点。

order

逻辑标量，指示是否返回顶点的 DFS 排序。

order.out

逻辑标量，指示是否基于离开顶点的子树来返回排序。

parent

逻辑标量，指示是否返回顶点的父节点。

dist

逻辑标量，指示是否返回搜索树的根的距离。

in.callback

如果不是 NULL，则它必须是回调函数。 每当访问一个顶点时，都会调用此函数。 请参阅下面的详细信息。

out.callback

如果不是 NULL，则它必须是回调函数。 当算法完成顶点的子树时，将调用此函数。 请参阅下面的详细信息。

extra

要提供给回调函数的附加参数。

rho

评估回调函数的环境。

neimode

[Deprecated] 此参数已从 igraph 1.3.0 中弃用； 请改用 mode。

father

[Deprecated]，请改用 parent。

值

一个带有以下条目的命名列表

root

数值标量。 用作搜索起点的根顶点。

neimode

字符标量。 函数调用的 mode 参数。 请注意，对于无向图，无论提供的值如何，这始终是“all”。

order

数值向量。 顶点 ID，按照它们被搜索访问的顺序排列。

order.out

数值向量，顶点 ID，按其子树完成的顺序排列。

parent

数值向量。 每个顶点的父节点，即它从中发现的顶点。

father

类似于 parent，目前为了兼容性而保留。

dist

数值向量，对于每个顶点，它是距搜索树根的距离。

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

详细信息

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

graph

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

data

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

extra

额外的参数。

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

参见

bfs() 用于广度优先搜索。

其他 structural.properties：bfs()、component_distribution()、connect()、constraint()、coreness()、degree()、distance_table()、edge_density()、feedback_arc_set()、feedback_vertex_set()、girth()、is_acyclic()、is_dag()、is_matching()、k_shortest_paths()、knn()、reciprocity()、subcomponent()、subgraph()、topo_sort()、transitivity()、unfold_tree()、which_multiple()、which_mutual()

作者

Gabor Csardi csardi.gabor@gmail.com

示例


## A graph with two separate trees
dfs(
  graph = make_tree(10) %du% make_tree(10),
  root = 1, mode = "out",
  unreachable = TRUE,
  order = TRUE,
  order.out = TRUE,
  parent = TRUE
)
#> $root
#> [1] 1
#> 
#> $mode
#> [1] "out"
#> 
#> $order
#> + 20/20 vertices, from 3ed9c7c:
#>  [1]  1  2  4  8  9  5 10  3  6  7 11 12 14 18 19 15 20 13 16 17
#> 
#> $order.out
#> + 20/20 vertices, from 3ed9c7c:
#>  [1]  8  9  4 10  5  2  6  7  3  1 18 19 14 20 15 12 16 17 13 11
#> 
#> $parent
#> + 20/20 vertices, from 3ed9c7c:
#>  [1] NA  1  1  2  2  3  3  4  4  5 NA 11 11 12 12 13 13 14 14 15
#> 
#> $dist
#> NULL
#> 
#> $neimode
#> [1] "out"
#> 
#> $father
#> + 20/20 vertices, from 3ed9c7c:
#>  [1] NA  1  1  2  2  3  3  4  4  5 NA 11 11 12 12 13 13 14 14 15
#> 

## 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(
  graph = make_tree(10),
  root = 1, mode = "out",
  in.callback = f.in, out.callback = f.out
)
#> in: 1, 0 
#> in: 2, 1 
#> in: 4, 2 
#> in: 8, 3 
#> out: 8, 2 
#> in: 9, 3 
#> out: 9, 2 
#> out: 4, 1 
#> in: 5, 2 
#> in: 10, 3 
#> out: 10, 2 
#> out: 5, 1 
#> out: 2, 0 
#> in: 3, 1 
#> in: 6, 2 
#> out: 6, 1 
#> in: 7, 2 
#> out: 7, 1 
#> out: 3, 0 
#> out: 1, -1 

## Terminate after the first component, using a callback
f.out <- function(graph, data, extra) {
  data["vid"] == 1
}
tmp <- dfs(
  graph = make_tree(10) %du% make_tree(10),
  root = 1,
  out.callback = f.out
)