BreadthFirstScan
BreadthFirstScan
BreadthFirstScan[g,s,{"event1"f1,"event2"f2,…}]
执行图 g 的广度优先搜索，以顶点 s 为起始点，每次出现 "eventi" 时计算 fi.
BreadthFirstScan[g,{"event1"f1,"event2"f2,…}]
执行整个图 g 的广度优先搜索.
BreadthFirstScan[{vw,…},…]
使用 vw 规则来指定图 g.
更多信息
- BreadthFirstScan 广度优先扫描也称为广度优先搜索（BFS）或广度优先遍历.
- BreadthFirstScan[g,s,{…}] 以广度优先顺序访问图 g 中与顶点 s 相连接的顶点.
- 广度优先搜索首先访问与当前被访问的顶点相邻接的所有顶点.
- BreadthFirstScan[g,{…}] 在 g 的顶点列表中从第一个顶点开始执行多个广度优先搜索，然后从顶点列表中第一个未被访问的顶点开始，搜索每个连接的分量.
- BreadthFirstScan[g,…] 给出表示一棵树的 {w1,w2,…} 的列表，其中 wi 是 vi 的前趋结点，而{v1,v2,…} 是 g 的顶点列表.
- 提供对顶点的探索的事件包括：
-
"DiscoverVertex" 当找到顶点时 "UnvisitedVertex" 当未访问顶点被再次找到时 "VisitedVertex" 当已访问顶点被再次找到时 - 当顶点 u 从已访问顶点 v 被发现，并且 v 距离起始顶点 s 的距离为 d 时，"DiscoverVertex"->fd 调用 fd[u,v,d].
- 当未访问顶点 u 从已访问顶点 v 中再次找到时，"UnvisitedVertex"->fru 调用 fru[u,v].
- 当已访问顶点 u 从已访问顶点 v 中再次找到时，"VisitedVertex"->frv 调用 frv[u,v].
- 提供对顶点的访问的选项包括：
-
"PrevisitVertex" 在访问一个顶点之前 "PostvisitVertex" 在访问一个顶点之后 - 在顶点 u 被访问之前，"PrevisitVertex"->fs 调用 fs[u].
- 在顶点 u 被访问之后，"PostvisitVertex"->fe 调用 fe[u].
- 一棵广度优先树是由在广度优先搜索中所遍历的边生成的树.
- 提供对从已访问顶点开始的边的搜索的选项包括：
-
"FrontierEdge" 在广度优先搜索树中的边 "CycleEdge" 不在广度优先搜索树中的边 - 对于边 vu，"FrontierEdge"->ffe 调用 ffe[vu]，其中顶点 v 正在被访问，u 还未被访问过. 通常对扫描广度优先搜索树是很有用的.
- 对于边 vu，"CycleEdge"->fce 调用 fce[vu]，其中顶点 v 正在被访问，u 已经被访问过. 通常对寻找不位于广度优先搜索树中的环或者边是很有用的.
- 对于一个无向图，用于 callback 的边是无向边 vu.
范例
打开所有单元 关闭所有单元基本范例 (2)
BreadthFirstScan[[image], 1, {"PrevisitVertex" -> (Print["Visiting ", #]&)}];
GridGraph[{3, 5}, VertexSize -> {5 -> Medium}]Reap[BreadthFirstScan[%, 5, {"FrontierEdge" -> Sow}]][[2, 1]]//HighlightGraph[%, #]&范围 (18)
基本用途 (6)
Reap[BreadthFirstScan[[image], 1, {"FrontierEdge" -> Sow}]][[2, 1]]BreadthFirstScan 可用于无向图：
g = [image];HighlightGraph[%,
Reap[BreadthFirstScan[%, 1, {"FrontierEdge" -> Sow}]][[2, 1]]]g = [image];HighlightGraph[g,
Reap[BreadthFirstScan[g, 1, {"FrontierEdge" -> Sow}]][[2, 1]]]g = {21, 14, 51, 32, 62, 34, 37, 48, 65, 76, 87, 85};HighlightGraph[g,
Reap[BreadthFirstScan[g, 1, {"FrontierEdge" -> Sow}]][[2, 1]]]如果忽略起始顶点，BreadthFirstScan 搜索整个图：
Reap[BreadthFirstScan[[image], {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]BreadthFirstScan 适用于大规模图：
g = GridGraph[{10, 10, 10, 10}];Timing[BreadthFirstScan[g, 1]//Length]顶点访问过程 (2)
g = PetersenGraph[5, 2]Reap[BreadthFirstScan[g, 1, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]Reap[BreadthFirstScan[g, 1, {"PrevisitVertex" -> Sow}]][[2, 1]]g = PetersenGraph[4, 1]Reap[BreadthFirstScan[g, 1, {"PrevisitVertex" -> (Sow["(" <> ToString[#] <> " "]&),
"PostvisitVertex" -> (Sow[ToString[#] <> ") "]&)}]][[2, 1]]边查找过程 (2)
"FrontierEdge" 用于可产生未搜索过的顶点的边：
g = [image];StringJoin@@Reap[BreadthFirstScan[g, 1, {"FrontierEdge" -> (Sow["Frontier: " <> ToString[#] <> ". "]&), "PrevisitVertex" -> (Sow["Start visit " <> ToString[#] <> ". "]&), "PostvisitVertex" -> (Sow["Finish " <> ToString[#] <> ".
"]&)}]][[2, 1]]print[g0_ ? GraphQ] :=
Module[{g = g0}, With[{str = StringJoin@@Reap[BreadthFirstScan[g, 1, {"CycleEdge" -> (Sow["Cycle edge: " <> ToString[#] <> ". "]&), "PrevisitVertex" -> (Sow["Start visit " <> ToString[#] <> ". "]&), "PostvisitVertex" -> (Sow["Finish " <> ToString[#] <> ".
"]&),
"FrontierEdge" -> ((AnnotationValue[{g, #}, EdgeStyle] = Directive[Arrowheads[Medium], Thick, StandardGray])&)}]][[2, 1]]}, Print[g];Print[str]]]print[[image]]
print[[image]]
顶点查找过程 (3)
当一个顶点被第一次找到，"DiscoverVertex" 事件被触发：
StringJoin@@Reap[BreadthFirstScan[[image], 1, {"DiscoverVertex" -> (Sow["Discover: " <> ToString[#1] <> ". "]&), "PrevisitVertex" -> (Sow["
Start visit " <> ToString[#] <> ". "]&), "PostvisitVertex" -> (Sow["Finish " <> ToString[#] <> "."]&)}]][[2, 1]]当探索已访问过的顶点时，"VisitedVertex" 事件被触发：
StringJoin@@Reap[BreadthFirstScan[[image], 1, {"VisitedVertex" -> (Sow["Visited: " <> ToString[#1] <> ". "]&), "PrevisitVertex" -> (Sow["Start visit " <> ToString[#] <> ". "]&), "PostvisitVertex" -> (Sow["Finish " <> ToString[#] <> ".
"]&)}]][[2, 1]]对于已经找到但尚未访问的顶点，"UnvisitedVertex" 事件被触发：
StringJoin@@Reap[BreadthFirstScan[[image], 1, {"UnvisitedVertex" -> (Sow["Unvisited: " <> ToString[#1] <> ". "]&), "PrevisitVertex" -> (Sow["Start visit " <> ToString[#] <> ". "]&), "PostvisitVertex" -> (Sow["Finish " <> ToString[#] <> ".
"]&)}]][[2, 1]]搜索树的前趋结点 (5)
BreadthFirstScan 返回广度优先搜索树中前趋结点的列表：
BreadthFirstScan[[image], 7]g = [image];BreadthFirstScan[g, 7]Thread[%VertexList[g]]HighlightGraph[g, Cases[%, u_v_ /; u =!= v]]当搜索产生一棵生成树时，TreeGraph 更加便捷：
g = [image];HighlightGraph[g, TreeGraph[VertexList[g], BreadthFirstScan[g, 7]]]前趋结点也可以通过 "DiscoverVertex" 事件得到：
g = [image];使用 VertexList 初始化，并且当找到一个顶点时，重新赋值：
pre = VertexList[g];BreadthFirstScan[g, 7, {"DiscoverVertex" -> ((pre[[VertexIndex[g, #1]]] = #2)&)}];
pre与 BreadthFirstScan 返回的值相比较：
% === BreadthFirstScan[g, 7]广度优先搜索树也可以通过 "FrontierEdge" 事件得到：
g = [image];Reap[BreadthFirstScan[g, 7, {"FrontierEdge" -> Sow}]][[2, 1]]HighlightGraph[g, %]选项 (42)
"CycleEdge" (8)
在 "OutEdges" 之后，每条边或者传递给 "FrontierEdge" 或者传递给 "CycleEdge"：
g = [image];当且仅当一条边产生第一次搜索的顶点时，触发 "FrontierEdge"：
BreadthFirstScan[g, 1, {"DiscoverVertex" -> (Print["Discover: ", #1]&), "OutEdges" -> (Print["Out-edge: ", #]&), "FrontierEdge" -> (Print["Frontier edge: ", #]&), "CycleEdge" -> (Print["Cycle edge: ", #]&)}];
在 "CycleEdge" 之后，触发 "VisitedVertex" 或者 "UnvisitedVertex"：
g = [image];当且仅当相邻的顶点已经被访问时，触发 "VisitedVertex"：
BreadthFirstScan[g, 1, {"CycleEdge" -> (Print["Cycle edge: ", #]&), "VisitedVertex" -> (Print["Revisiting visited: ", #]&), "UnvisitedVertex" -> (Print["Revisiting unvisited: ", #]&)}];
在一棵有向树中，标明对 "CycleEdge" 函数的调用：
g = [image];Reap[BreadthFirstScan[g, 1, {"CycleEdge" -> Sow}]][[2]]g = [image];Reap[BreadthFirstScan[g, 1, {"CycleEdge" -> Sow}]][[2, 1]]Sort[Sort /@ %] === Sort[Sort /@ EdgeList[g]]在一个有向 CycleGraph 中：
g = [image];Reap[BreadthFirstScan[g, 1, {"CycleEdge" -> Sow}]][[2, 1]]在一个无向 CycleGraph 中：
g = [image];Reap[BreadthFirstScan[g, 1, {"CycleEdge" -> Sow}]][[2, 1]]{Length[%], EdgeCount[g]}g = [image];Reap[BreadthFirstScan[g, 1, {"CycleEdge" -> Sow}]][[2, 1]]HighlightGraph[g, %]g = [image];Reap[BreadthFirstScan[g, 1, {"CycleEdge" -> Sow}]][[2, 1]]{Length[%], EdgeCount[g]}"DiscoverVertex" (8)
在 "FrontierEdge" 之后，对相邻的顶点触发 "DiscoverVertex"：
g = [image];BreadthFirstScan[g, 1, {"FrontierEdge" -> (Print["Frontier edge: ", #]&), "DiscoverVertex" -> (Print["Discover ", #1, " from ", #2, " at distance ", #3]&)}];
当一个顶点第一次被搜索时，触发 "DiscoverVertex" 事件：
g = [image];dv[u_, v_, d_] := Sow[u]Reap[BreadthFirstScan[g, 1, {"DiscoverVertex" -> dv}]][[2, 1]]"DiscoverVertex" 事件在对 "PrevisitVertex" 进行调用之前触发：
Reap[BreadthFirstScan[g, 1, {"DiscoverVertex" -> (Sow["Discover " <> ToString[#1]]&), "PrevisitVertex" -> (Sow["Previsit " <> ToString[#]]&)}]][[2, 1]]在一棵有向树中，显示传递给 "DiscoverVertex" 函数的变量：
g = [image];print[u_, v_, d_] := Print[u, " discovered from ", v, " at distance ", d]BreadthFirstScan[g, 1, {"DiscoverVertex" -> print}];
g = [image];print[u_, v_, d_] := Print[u, " discovered from ", v, " at distance ", d]BreadthFirstScan[g, 1, {"DiscoverVertex" -> print}];
在一个有向 CycleGraph 中：
g = [image];print[u_, v_, d_] := Print[u, " discovered from ", v, " at distance ", d]BreadthFirstScan[g, 1, {"DiscoverVertex" -> print}];
在一个无向 CycleGraph 中：
g = [image];print[u_, v_, d_] := Print[u, " discovered from ", v, " at distance ", d]BreadthFirstScan[g, 1, {"DiscoverVertex" -> print}];
g = [image];print[u_, v_, d_] := Print[u, " discovered from ", v, " at distance ", d]BreadthFirstScan[g, 1, {"DiscoverVertex" -> print}];
g = [image];print[u_, v_, d_] := Print[u, " discovered from ", v, " at distance ", d]BreadthFirstScan[g, 1, {"DiscoverVertex" -> print}];
"FrontierEdge" (8)
在 "OutEdges" 后，每条边或者传递给 "FrontierEdge" 或者传递给 "CycleEdge"：
g = [image];当且仅当一条边产生的顶点第一次被搜索才触发 "FrontierEdge"：
BreadthFirstScan[g, 1, {"DiscoverVertex" -> (Print["Discover: ", #1]&), "OutEdges" -> (Print["Out-edge: ", #]&), "FrontierEdge" -> (Print["Frontier edge: ", #]&), "CycleEdge" -> (Print["Cycle edge: ", #]&)}];
在 "FrontierEdge" 之后，对相邻顶点触发 "DiscoverVertex"：
g = [image];BreadthFirstScan[g, 1, {"FrontierEdge" -> (Print["Frontier edge: ", #]&), "DiscoverVertex" -> (Print["Discover ", #1, " from ", #2, " at distance ", #3]&)}];
对一棵有向树中的每条边调用 "FrontierEdge" 函数：
g = [image];Reap[BreadthFirstScan[g, 1, "FrontierEdge" -> Sow]][[2, 1]]Sort[%] === Sort[EdgeList[g]]g = [image];Reap[BreadthFirstScan[g, 1, "FrontierEdge" -> Sow]][[2, 1]]Sort[Sort /@ %] === Sort[Sort /@ EdgeList[g]]突出显示一个有向 CycleGraph 中的广度优先搜索树：
g = [image];Reap[BreadthFirstScan[g, 1, {"FrontierEdge" -> Sow}]][[2, 1]]HighlightGraph[g, %]在一个无向 CycleGraph 中：
g = [image];Reap[BreadthFirstScan[g, 1, {"FrontierEdge" -> Sow}]][[2, 1]]HighlightGraph[g, %]g = [image];Reap[BreadthFirstScan[g, 1, {"FrontierEdge" -> Sow}]][[2, 1]]HighlightGraph[g, %]g = [image];Reap[BreadthFirstScan[g, 1, {"FrontierEdge" -> Sow}]][[2, 1]]HighlightGraph[g, %]"PostvisitVertex" (2)
"PostvisitVertex" 是在一次顶点访问中最后触发的事件：
g = [image];与 "DiscoverVertex" 相似，它可以用于求顶点的广度优先顺序：
Reap[BreadthFirstScan[g, 1, {"PostvisitVertex" -> Sow}]][[2, 1]]在 "PostvisitVertex" 后，队列中的下一个未访问顶点继续访问过程：
Reap[BreadthFirstScan[g, 1, {"PrevisitVertex" -> (Sow["Previsit " <> ToString[#]]&), "PostvisitVertex" -> (Sow["Postvisit " <> ToString[#]]&)}]][[2, 1]]"PrevisitVertex"、"PostvisitVertex" 和 "DiscoverVertex" 的相对顺序：
g = [image];Reap[BreadthFirstScan[g, 1, {"DiscoverVertex" -> (Sow["Discover " <> ToString[#1]]&), "PrevisitVertex" -> (Sow["Previsit " <> ToString[#1]]&), "PostvisitVertex" -> (Sow["Postvisit " <> ToString[#1]]&)}]][[2, 1]]"PrevisitVertex" (2)
在每次顶点访问开始时，触发 "PrevisitVertex" 事件：
g = [image];与 "DiscoverVertex" 相似，它可以用来找到顶点的广度优先排序：:
Reap[BreadthFirstScan[g, 1, {"PrevisitVertex" -> Sow} ]][[2, 1]]在调用 "DiscoverVertex" 后的某个时间触发 "PrevisitVertex"：
Reap[BreadthFirstScan[g, 1, {"DiscoverVertex" -> (Sow["Discover " <> ToString[#1]]&), "PrevisitVertex" -> (Sow["Previsit " <> ToString[#]]&)}]][[2, 1]]"PrevisitVertex"、"PostvisitVertex" 和 "DiscoverVertex" 的相对顺序：
g = [image];Reap[BreadthFirstScan[%, 1, {"DiscoverVertex" -> (Sow["Discover " <> ToString[#1]]&), "PrevisitVertex" -> (Sow["Previsit " <> ToString[#1]]&), "PostvisitVertex" -> (Sow["Postvisit " <> ToString[#1]]&)}]][[2, 1]]"UnvisitedVertex" (7)
在 "CycleEdge" 后，或者触发 "VisitedVertex" 或者触发 "UnvisitedVertex"：
g = [image];当且仅当相邻的顶点还未被访问时，触发 "UnvisitedVertex"：
BreadthFirstScan[%, 1, {"CycleEdge" -> (Print["Cycle edge: ", #]&), "VisitedVertex" -> (Print["Revisiting visited: ", #]&), "UnvisitedVertex" -> (Print["Revisiting unvisited: ", #]&)}];
在一棵有向树中标明传递给 "UnvisitedVertex" 函数的前趋：
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"UnvisitedVertex" -> print}];g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"UnvisitedVertex" -> print}];在有向的 CycleGraph 中：
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"UnvisitedVertex" -> print}];在无向的 CycleGraph 中：
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"UnvisitedVertex" -> print}];
g = [image];print[u_, v_] := Print[u, " revisited from ", v]在已发现的顶点被访问之前，它可能会被重新发现零次、一次或更多次：
BreadthFirstScan[g, 1, {"UnvisitedVertex" -> print}];
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"UnvisitedVertex" -> print}];
"VisitedVertex" (7)
在 "CycleEdge" 后，触发 "VisitedVertex" 或者 "UnvisitedVertex"：
g = [image];当且仅当相邻的顶点已经被访问才触发 "VisitedVertex"：
BreadthFirstScan[g, 1, {"CycleEdge" -> (Print["Cycle edge: ", #]&), "VisitedVertex" -> (Print["Revisiting visited: ", #]&), "UnvisitedVertex" -> (Print["Revisiting unvisited: ", #]&)}];
在一棵有向树中标明传递给 "VisitedVertex" 函数的前趋结点：
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"VisitedVertex" -> print}];g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"VisitedVertex" -> print}];
在一个有向 CycleGraph 中：
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"VisitedVertex" -> print}];
在一个无向 CycleGraph 中：
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"VisitedVertex" -> print}];
g = [image];print[u_, v_] := Print[u, " revisited from ", v]BreadthFirstScan[g, 1, {"VisitedVertex" -> print}];g = [image];print[u_, v_] := Print[u, " revisited from ", v]在一个顶点被访问之后，它可能重新被访问0次、1次或者更多次：
BreadthFirstScan[g, 1, {"VisitedVertex" -> print}];
应用 (17)
基本应用 (10)
outComponent[g_ ? GraphQ, v_] /; VertexQ[g, v] :=
Reap[BreadthFirstScan[g, v, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]outComponent[[image], 2]outComponent[g_ ? GraphQ, v_] /; VertexQ[g, v] :=
Reap[BreadthFirstScan[g, v, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]outComponent[g_ ? GraphQ, vl_List] := Union@@Map[outComponent[g, #]&, vl]outComponent[[image], {2, 8}]inComponent[g_ ? GraphQ, v_] /; VertexQ[g, v] :=
Reap[BreadthFirstScan[ReverseGraph[g], v, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]g = [image];{HighlightGraph[g, inComponent[g, 2]], HighlightGraph[g, inComponent[g, 3]]}connectedComponent[g_ ? UndirectedGraphQ, v_] /; VertexQ[g, v] :=
Reap[BreadthFirstScan[g, v, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]g = [image];HighlightGraph[g, connectedComponent[g, 9]]graphDistance[g_ ? GraphQ, s_, t_] /; VertexQ[g, s] && VertexQ[g, t] :=
Catch[BreadthFirstScan[g, s, {"DiscoverVertex" -> Function[{u, v, d}, If[u === t, Throw[d]]]}];∞]graphDistance[[image], 1, 12]s = 1;t = 3 * 4;
g = GridGraph[{3, 4}, VertexSize -> {s -> Medium, t -> Medium}]discoverFun[u_, v_, _] := If[u ≠ v, AnnotationValue[{g, u}, "Distance"] = AnnotationValue[{g, v}, "Distance"] + 1]AnnotationValue[{g, s}, "Distance"] = 0;BreadthFirstScan[g, s, {"DiscoverVertex" -> discoverFun}];提取目标处的距离，并且与 GraphDistance 相比较：
{AnnotationValue[{g, t}, "Distance"], GraphDistance[g, s, t]}g = [image];BreadthFirstScan[g, 1,
{"DiscoverVertex" -> (If[AnnotationValue[{g, #1}, VertexStyle] === Red, Throw[#1]]&)}]//Catchg = [image];Do[AnnotationValue[{g, v}, "count"] = 0, {v, VertexList[g]}];discover[v_, u_, _] /; u === v := (++AnnotationValue[{g, v}, "count"];Print["Starting scan at ", v])discover[v_, u_, _] /; u =!= v := (++AnnotationValue[{g, v}, "count"];Print["Discover ", v])BreadthFirstScan[g, "DiscoverVertex" -> discover];
Table[v -> AnnotationValue[{g, v}, "count"], {v, VertexList[g]}]g = [image];在一个无向图中，BreadthFirstScan 访问连通分量中的每个顶点：
Reap[BreadthFirstScan[g, 2, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]HighlightGraph[g, %]Do[AnnotationValue[{g, v}, "Visited"] = False, {v, VertexList[g]}];findComponent[start_] := Reap[BreadthFirstScan[g, start, {"DiscoverVertex" -> ((AnnotationValue[{g, #1}, "Visited"] = True;Sow[#1])&)}]][[2, 1]]Reap[Do[If[¬AnnotationValue[{g, start}, "Visited"], Sow[findComponent[start]]],
{start, VertexList[g]}]][[2, 1]]与 ConnectedComponents 相比较：
Sort[Sort /@ %] === Sort[Sort /@ ConnectedComponents[g]]g = GraphDisjointUnion[CompleteGraph[{2, 3}], CycleGraph[7]]Do[AnnotationValue[{g, v}, "Partition"] = 0, {v, VertexList[g]}];discover[u_, v_, _] /; u === v := AnnotationValue[{g, u}, "Partition"] = 1discover[u_, v_, _] /; u =!= v := AnnotationValue[{g, u}, "Partition"] = -AnnotationValue[{g, v}, "Partition"]rediscover[u_, v_] := If[AnnotationValue[{g, u}, "Partition"] == AnnotationValue[{g, v}, "Partition"], Throw[False]]如果可以搜索一个图，并且找不到任何不一致的地方，则这个图是二部图：
Catch[BreadthFirstScan[g, {"DiscoverVertex" -> discover, "VisitedVertex" -> rediscover, "UnvisitedVertex" -> rediscover}];True]显示搜索过程 (4)
利用 "FrontierEdge" 构建一个广度优先搜索树：
g = GridGraph[{3, 4}, VertexSize -> {2 -> Medium}]Reap[BreadthFirstScan[g, 2, {"FrontierEdge" -> Sow}]][[2, 1]]HighlightGraph[g, %]在一个有向图中，"CycleEdge" 边可以归类为后边（back edges）或者交叉边（cross edges）：
backEdgeQ[g_, v_a_] := Catch[Module[{t = v, p}, While[True, If[t === a, Throw[True]];
p = AnnotationValue[{g, t}, "Pre"];
If[p === t, Throw[False], t = p]]]]color[g0_ ? GraphQ, v_] /; VertexQ[g0, v] :=
Module[{g = g0},
BreadthFirstScan[g, 1, {"DiscoverVertex" -> ((AnnotationValue[{g, #1}, "Pre"] = #2)&), "FrontierEdge" -> ((AnnotationValue[{g, #}, EdgeStyle] = Directive[Arrowheads[Small], Thick, Black])&), "CycleEdge" -> ((AnnotationValue[{g, #}, EdgeStyle] = If[backEdgeQ[g, #], Directive[Arrowheads[Small], Blue], Directive[Arrowheads[Small], Black, Dashed]])&)}];
g]{color[[image], 1], color[[image], 1]}在每个顶点的时间轴中，在搜索的时间处放置一个点，从 previsit 到 postvisit 处放置一条线：
vertexTimeline[data_] := With[{p = First /@ Position[data, True], tMax = 25}, Graphics[{Gray, Thin, Line[{{0, 0}, {tMax + 1, 0}}], StandardGray, Thick, Disk[{p[[1]], 0}, 0.2], Line[{{p[[2]], 0}, {If[Length[p] == 3, p[[3]], tMax + 1], 0}}]}, PlotRange -> {{0, tMax + 1}, {-0.5, 0.5}}, ImageSize -> 400]]graphTimelines[g_, start_] :=
With[{data = Reap[BreadthFirstScan[g, start, {"DiscoverVertex" -> (Sow[{#1, "", ""}]&), "PrevisitVertex" -> (Sow[{"", #1, ""}]&), "PostvisitVertex" -> (Sow[{"", "", #1}]&)}]][[2, 1]]}, TableForm[Table[vertexTimeline[Thread[Or@@Map[# === v&, data, {2}]]], {v, VertexList[g]}], TableHeadings -> {VertexList[g], None}]]graphTimelines[[image], 1]graphTimelines[[image], 1]在一个有向 CycleGraph：
graphTimelines[[image], 1]在一个无向 CycleGraph 中：
graphTimelines[[image], 1]graphTimelines[[image], 1]graphTimelines[[image], 1]Dynamic[g, Initialization :> (g = Annotate[[image], ImageSize -> 150];)]把搜索过的顶点变为红色，活动中的顶点变为黄色，访问过的顶点变为蓝色，将不是树的边颜色用来显示它们是否产生 "UnvisitedVertex" （红色）或者 "VisitedVertex" （蓝色）调用：
pause := Pause[0.5]BreadthFirstScan[g, 1, {"DiscoverVertex" -> ((AnnotationValue[{g, #1}, VertexStyle] = Red;pause)&), "PrevisitVertex" -> ((AnnotationValue[{g, #}, VertexStyle] = Yellow;pause)&), "PostvisitVertex" -> ((AnnotationValue[{g, #}, VertexStyle] = Blue;pause)&), "FrontierEdge" -> ((AnnotationValue[{g, #}, EdgeStyle] = Directive[Arrowheads[Small], Dashing[{}], Thick, StandardGray];pause)&), "UnvisitedVertex" -> ((AnnotationValue[{g, #2#1}, EdgeStyle] = Directive[Arrowheads[Small], Dashing[{}], Red];pause)&), "VisitedVertex" -> ((AnnotationValue[{g, #2#1}, EdgeStyle] = Directive[Arrowheads[Small], Dashing[{}], Blue];pause)&)}];最短路径应用 (3)
s = 1;
t = 3 * 4;
g = GridGraph[{3, 4}, VertexSize -> {s -> Medium, t -> Medium}]discoverFun[u_, v_, d_] := If[u ≠ v, AnnotationValue[{g, u}, "Predecessor"] = v]BreadthFirstScan[g, s, {"DiscoverVertex" -> discoverFun}];Reap[Module[{v = t}, While[v ≠ s, Sow[v];v = AnnotationValue[{g, v}, "Predecessor"]];Sow[v]]][[2, 1]]//Reverse与 FindShortestPath 相比较：
{HighlightGraph[g, PathGraph[%]], HighlightGraph[g, PathGraph@FindShortestPath[g, s, t]]}s = 1;
t = 3 * 4;
g = GridGraph[{3, 4}, VertexSize -> {s -> Medium, t -> Medium}]discoverFun[u_, v_, d_] := If[u ≠ v, AnnotationValue[{g, u}, "ShortestPaths"] = Table[Append[p, u], {p, AnnotationValue[{g, v}, "ShortestPaths"]}];AnnotationValue[{g, u}, "Distance"] = d]revisitFun[u_, v_] := If[AnnotationValue[{g, u}, "Distance"] == AnnotationValue[{g, v}, "Distance"] + 1, AnnotationValue[{g, u}, "ShortestPaths"] = Join[AnnotationValue[{g, u}, "ShortestPaths"], Table[Append[p, u], {p, AnnotationValue[{g, v}, "ShortestPaths"]}]]]AnnotationValue[{g, s}, "ShortestPaths"] = {{s}};
AnnotationValue[{g, s}, "Distance"] = 0;BreadthFirstScan[g, s, {"DiscoverVertex" -> discoverFun, "VisitedVertex" -> revisitFun, "UnvisitedVertex" -> revisitFun}];Table[HighlightGraph[g, p], {p, PathGraph /@ AnnotationValue[{g, t}, "ShortestPaths"]}]在一个空手道俱乐部中，Zachary 的传统友谊网络的中介中心性：
g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}]discoverFun[u_, v_, d_] := (If[u =!= v, AnnotationValue[{g, u}, "ShortestPathCount"] = AnnotationValue[{g, v}, "ShortestPathCount"]];
AnnotationValue[{g, u}, "Distance"] = d)revisitFun[u_, v_] := If[AnnotationValue[{g, u}, "Distance"] == AnnotationValue[{g, v}, "Distance"] + 1, AnnotationValue[{g, u}, "ShortestPathCount"] += AnnotationValue[{g, v}, "ShortestPathCount"]]在考虑从每个顶点的所有最短路径时，对 "BetweennessCentrality" 进行累积：
Do[AnnotationValue[{g, v}, "BetweennessCentrality"] = 0, {v, VertexList[g]}];Do[Do[AnnotationValue[{g, v}, "ShortestPathCount"] = 0, {v, VertexList[g]}];AnnotationValue[{g, s}, "ShortestPathCount"] = 1;BreadthFirstScan[g, s, {"DiscoverVertex" -> discoverFun, "VisitedVertex" -> revisitFun, "UnvisitedVertex" -> revisitFun}];
Do[With[{score = Total[Table[(AnnotationValue[{g, v}, "ShortestPathCount"]/AnnotationValue[{g, u}, "ShortestPathCount"])AnnotationValue[{g, u}, "PathScore"], {u, Select[EdgeList[g, v_] /. {vu_ :> u, u_v :> u}, AnnotationValue[{g, #}, "Distance"] > AnnotationValue[{g, v}, "Distance"]&]}]]},
AnnotationValue[{g, v}, "PathScore"] = score + 1;AnnotationValue[{g, v}, "BetweennessCentrality"] += score], {v, Most@SortBy[VertexList[g], -AnnotationValue[{g, #}, "Distance"]&]}], {s, VertexList[g]}]scores = Table[AnnotationValue[{g, v}, "BetweennessCentrality"], {v, VertexList[g]}];
Plot[Count[scores, _ ? (# ≤ x&)], {x, 0, Max[scores] + 1}, PlotRange -> {0, Length[scores]}, GridLines -> {None, Automatic}, Filling -> Axis]以中介中心性为顺序对顶点进行排序（1 是管理员，而 34 是教员）：
SortBy[VertexList[g], AnnotationValue[{g, #}, "BetweennessCentrality"]&]HighlightGraph[g, %[[-2 ;; ]]]属性和关系 (4)
Reap[BreadthFirstScan[[image], 1,
{"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]Reap[BreadthFirstScan[[image], 1,
{"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]Reap[BreadthFirstScan[[image], 1,
{"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]g = [image];ConnectedComponents[g]Reap[BreadthFirstScan[g, 1, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]Reap[BreadthFirstScan[g, 4, {"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]Reap[BreadthFirstScan[[image], 4,
{"DiscoverVertex" -> (Sow[#1]&)}]][[2, 1]]
Wolfram Research (2010)，BreadthFirstScan，Wolfram 语言函数，https://reference.wolfram.com/language/ref/BreadthFirstScan.html （更新于 2015 年）.
文本
Wolfram Research (2010)，BreadthFirstScan，Wolfram 语言函数，https://reference.wolfram.com/language/ref/BreadthFirstScan.html （更新于 2015 年）.
CMS
Wolfram 语言. 2010. "BreadthFirstScan." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/BreadthFirstScan.html.
APA
Wolfram 语言. (2010). BreadthFirstScan. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/BreadthFirstScan.html 年