MATHEMATICA 組込みシンボル

BreadthFirstScan

BreadthFirstScan[g, s, {"event₁"->f₁, "event₂"->f₂, ...}]
グラフ g の幅優先探索(bfs)を頂点 s から始めて行い，が起るたびにを評価する．

BreadthFirstScan[g, {"event₁"->f₁, "event₂"->f₂, ...}]
グラフ g 全体の幅優先探索を行う．　

詳細 詳細

BreadthFirstScan[g, s, {...}]は，幅優先順に頂点 s に連結されているグラフ g 内の頂点を訪れる．
幅優先順では，現在訪れられている頂点に隣接した頂点すべてがまず訪れられる．
BreadthFirstScan[g, {...}]は，g の頂点リストの最初の頂点から始めて，複数の幅優先探索を行い，その後まだ訪れていない頂点リストの最初の頂点から始めることにより，事実上それぞれの連結成分を探索する．
BreadthFirstScan[g, ...]は，がに先行するものであり，が g の頂点リストである木を表すリストを与える．
頂点の発見にアクセスを提供する事象：

"DiscoverVertex"->fd は，開始頂点 s からの距離 d の地点で頂点 u が訪れられた頂点 v から見付けられるとき，を呼び出す．
"UnvisitedVertex"->fru は，訪れていない頂点 u が訪れた頂点 v からもう一度見付けられる場合に，を呼び出す．
"VisitedVertex"->frv は，訪れた頂点 u が訪れた頂点 v からもう一度見付けられる場合に，を呼び出す．
頂点の訪問へのアクセスを提供する事象：
"PrevisitVertex" 頂点を訪れる前

"PostvisitVertex" 頂点を訪れた後
"PrevisitVertex"->fs は頂点 u を訪れる前にを呼び出す．
"PostvisitVertex"->fe は頂点 u を訪れた後にを呼び出す．
幅優先探索の木は，幅優先探索の際に走査された辺によって生成される木である．
訪れた頂点から辺の探査へのアクセスを提供する事象：
"FrontierEdge" 幅優先探索の木の辺

"CycleEdge" 幅優先探索の木にない辺
"FrontierEdge"->ffe は，頂点 v が訪れられていて，u がまだ見付けられていない場合の辺についてを呼び出す．
"CycleEdge"->fce は，頂点 v が訪れられていて，u がもう見付けられた場合の辺についてを呼び出す．通常幅優先探索の木にない閉路や辺を見付けるのに便利である．
無向グラフについては，呼び出しに使われる辺は無向の辺であると見なされる．