R igraph 手册页

bfs {igraph}

R 文档

广度优先搜索

描述

广度优先搜索是一种遍历图的算法。我们从一个根顶点开始，并“同时”沿着每条边扩展。

用法

bfs(
  graph,
  root,
  mode = c("out", "in", "all", "total"),
  unreachable = TRUE,
  restricted = NULL,
  order = TRUE,
  rank = FALSE,
  father = FALSE,
  pred = FALSE,
  succ = FALSE,
  dist = FALSE,
  callback = NULL,
  extra = NULL,
  rho = parent.frame(),
  neimode
)

参数

图	输入图。
root	数值向量，通常长度为 1。根顶点，或开始搜索的根顶点。
模式	对于有向图，指定要遵循的边的类型。“out” 遵循外向边，“in” 遵循内向边。“all” 完全忽略边方向。“total” 是 “all” 的同义词。此参数对于无向图将被忽略。
unreachable	逻辑标量，搜索是否应访问从给定根顶点（或顶点）无法到达的顶点。如果 TRUE，则执行额外的搜索直到访问所有顶点。
restricted	NULL（=无限制），或顶点向量（id 或符号名称）。在后一种情况下，搜索仅限于给定的顶点。
order	逻辑标量，是否返回顶点的排序。
rank	逻辑标量，是否返回顶点的等级。
father	逻辑标量，是否返回顶点的父节点。
pred	逻辑标量，是否返回顶点的前驱节点。
succ	逻辑标量，是否返回顶点的后继节点。
dist	逻辑标量，是否返回从搜索树的根节点到顶点的距离。
callback	如果不是 NULL，则必须是回调函数。每当访问一个顶点时都会调用它。请参阅下面的详细信息。
extra	提供给回调函数的附加参数。
rho	评估回调函数的环境。
neimode	从 igraph 1.3.0 开始，此参数已被弃用；请改用 mode。

详细信息

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

图

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

数据

一个命名的数值向量，包含以下条目：“vid”，刚刚访问的顶点，“pred”，它的前驱节点（如果是第一个顶点则为零），“succ”，它的后继节点（如果是最后一个顶点则为零），“rank”，当前顶点的等级，“dist”，它与搜索树的根节点的距离。

extra

extra 参数。

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

值

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

root	数值标量。用作搜索起点的根顶点。
neimode	字符标量。函数调用的 mode 参数。请注意，对于无向图，无论提供的具体值是什么，它始终为 “all”。
order	数值向量。顶点 id，按照搜索访问它们的顺序排列。
rank	数值向量。每个顶点的等级。
father	数值向量。每个顶点的父节点，即发现它的顶点。
pred	数值向量。每个顶点先前访问的顶点，如果不存在这样的顶点，则为 0。
succ	数值向量。当前顶点之后访问的下一个顶点，如果不存在这样的顶点，则为 0。
dist	数值向量，对于每个顶点，它与搜索树的根节点的距离。

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

作者

Gabor Csardi csardi.gabor@gmail.com

参见

dfs 用于深度优先搜索。

示例

## Two rings
bfs(make_ring(10) %du% make_ring(10), root=1, "out",
          order=TRUE, rank=TRUE, father=TRUE, pred=TRUE,
          succ=TRUE, dist=TRUE)

## How to use a callback
f <- function(graph, data, extra) {
  print(data)
  FALSE
}
tmp <- bfs(make_ring(10) %du% make_ring(10), root=1, "out",
                 callback=f)

## How to use a callback to stop the search
## We stop after visiting all vertices in the initial component
f <- function(graph, data, extra) {
 data['succ'] == -1
}
bfs(make_ring(10) %du% make_ring(10), root=1, callback=f)

---