广度优先搜索是一种遍历图的算法。我们从一个根顶点开始，沿着每条边“同时”扩展。
用法
bfs(
graph,
root,
mode = c("out", "in", "all", "total"),
...,
unreachable = TRUE,
restricted = NULL,
order = TRUE,
rank = FALSE,
parent = FALSE,
pred = FALSE,
succ = FALSE,
dist = FALSE,
callback = NULL,
extra = NULL,
rho = parent.frame(),
neimode = deprecated(),
father = deprecated()
)参数
- graph
输入图。
- root
数值向量，通常长度为1。从其开始搜索的根顶点或根顶点。
- mode
对于有向图，指定要遵循的边的类型。“out”遵循出边，“in”遵循入边。“all”完全忽略边方向。“total”是“all”的同义词。 此参数对于无向图将被忽略。
- ...
这些点用于未来的扩展，并且必须为空。
- unreachable
逻辑标量，指示搜索是否应访问从给定根顶点（或多个顶点）无法访问的顶点。 如果为
TRUE，则执行额外的搜索，直到访问所有顶点。- restricted
NULL(=无限制)，或顶点向量（id或符号名称）。在后一种情况下，搜索仅限于给定的顶点。- order
逻辑标量，是否返回顶点的排序。
- rank
逻辑标量，是否返回顶点的等级。
- parent
逻辑标量，是否返回顶点的父节点。
- pred
逻辑标量，是否返回顶点的前驱。
- succ
逻辑标量，是否返回顶点的后继。
- dist
逻辑标量，指示是否返回搜索树的根的距离。
- callback
如果不是
NULL，则它必须是回调函数。 每当访问一个顶点时，都会调用此函数。 请参阅下面的详细信息。- extra
要提供给回调函数的附加参数。
- rho
评估回调函数的环境。
- neimode
![[Deprecated]](figures/lifecycle-deprecated.svg)
此参数已从 igraph 1.3.0 中弃用； 请改用 mode。- father
- 使用
parent代替。
值
一个包含以下条目的命名列表
- root
数值标量。用作搜索起点的根顶点。
- neimode
字符标量。函数调用的
mode参数。请注意，对于无向图，无论提供的价值如何，这始终为“all”。- order
数值向量。顶点ID，按照搜索访问它们的顺序。
- rank
数值向量。每个顶点的等级，对于无法访问的顶点为零。
- parent
数值向量。每个顶点的父节点，即发现它的顶点。
- father
像父节点一样，目前为了兼容性而保留。
- pred
数值向量。每个顶点的前一个访问顶点，如果没有这样的顶点，则为0。
- succ
数值向量。在当前顶点之后访问的下一个顶点，如果没有这样的顶点，则为0。
- dist
数值向量，对于每个顶点，它是与搜索树的根的距离。自igraph 1.6.0起，无法访问的顶点具有负距离，以前是
NaN。
请注意，如果相应的参数为FALSE，即如果不请求计算，则order，rank，parent，pred，succ和dist可能为NULL。
详细信息
回调函数必须具有以下参数
- graph
输入图在此处传递给回调函数。
- data
一个命名的数值向量，包含以下条目：“vid”，刚刚访问的顶点，“pred”，它的前驱（如果这是第一个顶点，则为零），“succ”，它的后继（如果这是最后一个顶点，则为零），“rank”，当前顶点的等级，“dist”，它与搜索树根的距离。
- extra
额外的参数。
回调必须返回FALSE以继续搜索或TRUE以终止搜索。请参阅下面的示例，了解如何使用回调函数。
参见
dfs() 用于深度优先搜索。
其他structural.properties：component_distribution()，connect()，constraint()，coreness()，degree()，dfs()，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
示例
## Two rings
bfs(make_ring(10) %du% make_ring(10),
root = 1, "out",
order = TRUE, rank = TRUE, parent = TRUE, pred = TRUE,
succ = TRUE, dist = TRUE
)
#> $root
#> [1] 1
#>
#> $mode
#> [1] "out"
#>
#> $order
#> + 20/20 vertices, from 735f4eb:
#> [1] 1 2 10 3 9 4 8 5 7 6 11 12 20 13 19 14 18 15 17 16
#>
#> $rank
#> [1] 1 2 4 6 8 10 9 7 5 3 11 12 14 16 18 20 19 17 15 13
#>
#> $parent
#> + 20/20 vertices, from 735f4eb:
#> [1] NA 1 2 3 4 5 8 9 10 1 NA 11 12 13 14 15 18 19 20 11
#>
#> $pred
#> + 20/20 vertices, from 735f4eb:
#> [1] NA 1 10 9 8 7 5 4 3 2 NA 11 20 19 18 17 15 14 13 12
#>
#> $succ
#> + 20/20 vertices, from 735f4eb:
#> [1] 2 10 9 8 7 NA 6 5 4 3 12 20 19 18 17 NA 16 15 14 13
#>
#> $dist
#> [1] 0 1 2 3 4 5 4 3 2 1 0 1 2 3 4 5 4 3 2 1
#>
#> $neimode
#> [1] "out"
#>
#> $father
#> + 20/20 vertices, from 735f4eb:
#> [1] NA 1 2 3 4 5 8 9 10 1 NA 11 12 13 14 15 18 19 20 11
#>
## 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
)
#> vid pred succ rank dist
#> 1 0 2 1 0
#> vid pred succ rank dist
#> 2 1 10 2 1
#> vid pred succ rank dist
#> 10 2 3 3 1
#> vid pred succ rank dist
#> 3 10 9 4 2
#> vid pred succ rank dist
#> 9 3 4 5 2
#> vid pred succ rank dist
#> 4 9 8 6 3
#> vid pred succ rank dist
#> 8 4 5 7 3
#> vid pred succ rank dist
#> 5 8 7 8 4
#> vid pred succ rank dist
#> 7 5 6 9 4
#> vid pred succ rank dist
#> 6 7 0 10 5
#> vid pred succ rank dist
#> 11 0 12 11 0
#> vid pred succ rank dist
#> 12 11 20 12 1
#> vid pred succ rank dist
#> 20 12 13 13 1
#> vid pred succ rank dist
#> 13 20 19 14 2
#> vid pred succ rank dist
#> 19 13 14 15 2
#> vid pred succ rank dist
#> 14 19 18 16 3
#> vid pred succ rank dist
#> 18 14 15 17 3
#> vid pred succ rank dist
#> 15 18 17 18 4
#> vid pred succ rank dist
#> 17 15 16 19 4
#> vid pred succ rank dist
#> 16 17 0 20 5
## 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)
#> $root
#> [1] 1
#>
#> $mode
#> [1] "out"
#>
#> $order
#> + 20/20 vertices, from 8b39c74:
#> [1] 1 2 10 3 9 4 8 5 7 6 11 12 20 13 19 14 18 15 17 16
#>
#> $rank
#> NULL
#>
#> $parent
#> NULL
#>
#> $pred
#> NULL
#>
#> $succ
#> NULL
#>
#> $dist
#> NULL
#>
#> $neimode
#> [1] "out"
#>