BreadthFirstScan
BreadthFirstScan
BreadthFirstScan[g,s,{"event1"f1,"event2"f2,…}]
グラフ g の幅優先探索(bfs)を頂点 s から始めて行い，"eventi" が起るたびに fiを評価する．
BreadthFirstScan[g,{"event1"f1,"event2"f2,…}]
グラフ g 全体の幅優先探索を行う．
BreadthFirstScan[{vw,…},…]
規則 vw を使ってグラフ g を指定する．
詳細
- BreadthFirstScanは，幅優先探索(BFS)あるいは横型探索としても知られている．
- BreadthFirstScan[g,s,{…}]は，幅優先順に頂点 s に連結されているグラフ g 内の頂点を訪れる．
- 幅優先順では，現在訪れられている頂点に隣接した頂点すべてがまず訪れられる．
- BreadthFirstScan[g,{…}]は，g の頂点リストの最初の頂点から始めて，複数の幅優先探索を行い，その後まだ訪れていない頂点リストの最初の頂点から始めることにより，事実上それぞれの連結成分を探索する．
- BreadthFirstScan[g,…]は，wiが viに先行するものであり，{v1,v2,…}が g の頂点リストである木を表すリスト{w1,w2,…}を与える．
- 頂点の発見にアクセスを提供する事象
-
"DiscoverVertex" いつ頂点が見付けられるか "UnvisitedVertex" いつ訪れていない頂点がもう一度見付けられるか "VisitedVertex" いつ訪れた頂点がもう一度見付けられるか - "DiscoverVertex"->fd は，開始頂点 s からの距離 d の地点で頂点 u が訪れられた頂点 v から見付けられるとき，fd[u,v,d]を呼び出す．
- "UnvisitedVertex"->fru は，訪れていない頂点 u が訪れた頂点 v からもう一度見付けられる場合に，fru[u,v]を呼び出す．
- "VisitedVertex"->frv は，訪れた頂点 u が訪れた頂点 v からもう一度見付けられる場合に，frv[u,v]を呼び出す．
- 頂点の訪問へのアクセスを提供する事象
-
"PrevisitVertex" 頂点を訪れる前 "PostvisitVertex" 頂点を訪れた後 - "PrevisitVertex"->fs は頂点 u を訪れる前に fs[u]を呼び出す．
- "PostvisitVertex"->fe は頂点 u を訪れた後に fe[u]を呼び出す．
- 幅優先探索の木は，幅優先探索の際に走査された辺によって生成される木である．
- 訪れた頂点から辺の探査へのアクセスを提供する事象
-
"FrontierEdge" 幅優先探索の木の辺 "CycleEdge" 幅優先探索の木にない辺 - "FrontierEdge"->ffe は，頂点 v が訪れられていて，u がまだ見付けられていない場合の辺 vu について ffe[vu]を呼び出す．
- "CycleEdge"->fce は，頂点 v が訪れられていて，u がもう見付けられた場合の辺 vu について fce[vu]を呼び出す．通常幅優先探索の木にない閉路や辺を見付けるのに便利である．
- 無向グラフについては，呼び出しに使われる辺は無向の辺 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]]"CycleEdge"は，見付けられた頂点に導く辺に対して引き起される：
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)&)}];
preBreadthFirstScanからの戻り値と比べる：
% === 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: ", #]&)}];
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];開始頂点に対しても"DiscoverVertex"が引き起される：
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];開始頂点に対しても"DiscoverVertex"が引き起される：
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]見付けられた頂点が訪問される前に，これはゼロ回，1回，あるいはそれ以上の回数再発見されることがある：
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]頂点が訪問された後，これはゼロ回，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]]各頂点について"Partition"の一貫した割当てを求めようとする：
Do[AnnotationValue[{g, v}, "Partition"] = 0, {v, VertexList[g]}];各頂点は，その先行頂点における値によって1あるいは-1の値を割り当てられる：
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"の辺は「後退辺」あるいは「交差辺」として分類することができる：
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, Red])&), "CycleEdge" -> ((AnnotationValue[{g, #}, EdgeStyle] = If[backEdgeQ[g, #], Directive[Arrowheads[Small], Blue], Directive[Arrowheads[Small], Red, Dashed]])&)}];
g]{color[[image], 1], color[[image], 1]}各頂点の時系列において，発見時に点を付け，訪問前から訪問後へ線を引く：
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]]//ReverseFindShortestPathと比べる：
{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]}]媒介中心性の累積分布は，2つの点数が際立っていることを示す：
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]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 Language. 2010. "BreadthFirstScan." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/BreadthFirstScan.html.
APA
Wolfram Language. (2010). BreadthFirstScan. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/BreadthFirstScan.html