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)

幅優先順に木の頂点を訪れる：

幅優先探索の木にハイライトを付ける：

スコープ  (18)

基本  (6)

事象を使って探索中にコードを実行する：

BreadthFirstScanは無向グラフに使える：

有向グラフ：

規則を使ってグラフを指定する：

開始頂点が省略されると，BreadthFirstScanはグラフ全体を見付ける：

BreadthFirstScanは大きいグラフに使うことができる：

頂点の訪問過程  (2)

頂点は見付けられた順に訪問される：

一度に1つの頂点だけ訪問される：

辺の発見過程  (2)

"FrontierEdge"は，見付けられていない頂点に導く辺に対して引き起される：

"CycleEdge"は，見付けられた頂点に導く辺に対して引き起される：

有向グラフにおいて：

無向グラフにおいて：

頂点の発見過程  (3)

"DiscoverVertex"の事象は，頂点がはじめて見付けられたときに引き起される：

"VisitedVertex"の事象は，すでに訪問された頂点を再訪問した場合に引き起される：

"UnvisitedVertex"の事象は，発見されたがまだ訪問されていない頂点によって引き起される：

探索の木で先行するもの  (5)

BreadthFirstScanは，幅優先探索の木における先行頂点のリストを返す：

先行するもののリストを使って幅優先探索の木を再構築することができる：

各頂点とその先行頂点の間の辺を構築する：

自己ループである辺は木の一部とはならない：

探索が全域木を作成する場合には，TreeGraphの方が便利である：

先行する頂点は"DiscoverVertex"の事象を使っても得ることができる：

VertexListで初期化し，頂点が見付かったときに値をもう一度割り当てる：

BreadthFirstScanからの戻り値と比べる：

幅優先探索の木は"FrontierEdge"の事象を使っても得ることができる：

オプション  (42)

"CycleEdge"  (8)

"OutEdges"の後で，各辺は"FrontierEdge"か"CycleEdge"に渡される：

辺がはじめて見付けられた頂点に繋がっている場合には，"FrontierEdge"が引き起される：

"CycleEdge"に続いて，"VisitedVertex"か"UnvisitedVertex"が引き起される：

隣接する頂点がすでに訪問された場合には，"VisitedVertex"が引き起される：

"CycleEdge"関数への呼出しを有向の木で示す：

このグラフについては事象は決して引き起されない：

無向の木において：

すべての辺について事象が引き起される：

有向のCycleGraphにおいて：

無向のCycleGraphにおいて：

辺によっては事象が2度以上引き起されることがある：

有向非巡回グラフにおいて：

巡回の辺をハイライトする：

格子グラフにおいて：

辺によっては2度以上事象が引き起される場合もある：

"DiscoverVertex"  (8)

"FrontierEdge"に続いて，隣接頂点に対して"DiscoverVertex"が引き起される：

開始頂点に対しても"DiscoverVertex"が引き起される：

頂点がはじめて見付けられた場合に"DiscoverVertex"の事象が引き起される：

これは頂点の幅優先順を求めるのに使うことができる：

"DiscoverVertex"事象が"PrevisitVertex"への呼出しの前に引き起される：

引数が有向の木で"DiscoverVertex"関数に渡されるのを示す：

無向の木において：

有向のCycleGraphにおいて：

無向のCycleGraphにおいて：

有向巡回グラフにおいて：

格子グラフにおいて：

"FrontierEdge"  (8)

"OutEdges"の後，各辺は"FrontierEdge"か"CycleEdge"に渡される：

辺がはじめて見付けられた頂点に繋がっている場合には，"FrontierEdge"が引き起される：

"FrontierEdge"に続いて，隣接頂点に対して"DiscoverVertex"が引き起される：

開始頂点に対しても"DiscoverVertex"が引き起される：

有向の木のそれぞれの辺すべてに対して"FrontierEdge"関数が呼び出される：

これは無向の木のそれぞれの辺すべてに対して呼び出される：

有向のCycleGraphの幅優先探索の木をハイライトする：

無向のCycleGraphにおいて：

有向巡回グラフにおいて：

格子グラフにおいて：

"PostvisitVertex"  (2)

"PostvisitVertex"は，頂点の訪問の最後に引き起される事象である：

"DiscoverVertex"と同様に，これを使って頂点の幅優先順を求めることができる：

"PostvisitVertex"の後，待ち行列の次の未訪問の頂点について訪問過程が続けられる：

"PrevisitVertex"，"PostvisitVertex"，"DiscoverVertex"の相対的な順序：

"PrevisitVertex"  (2)

"PrevisitVertex"の事象は，各頂点の訪問の最初に引き起される：

"DiscoverVertex"と同様に，これを使って頂点の幅優先順序を求めることができる：

"DiscoverVertex"への呼出しがあってからどこかの時点で"PrevisitVertex"が引き起される：

"PrevisitVertex"，"PostvisitVertex"，"DiscoverVertex"の相対的な順序：

"UnvisitedVertex"  (7)

"CycleEdge"の後，"VisitedVertex"か"UnvisitedVertex"が引き起される：

隣接頂点がすでに訪問されていない場合に，"UnvisitedVertex"が引き起される：

有向の木において先行頂点が"UnvisitedVertex"関数に渡されることを示す：

事象はこのグラフについては全く引き起されない：

無向の木において：

事象はこのグラフについては全く引き起されない：

有向のCycleGraphにおいて：

事象はこのグラフについては全く引き起されない：

無向のCycleGraphにおいて：

有向巡回グラフにおいて：

見付けられた頂点が訪問される前に，これはゼロ回，1回，あるいはそれ以上の回数再発見されることがある：

格子グラフにおいて：

"VisitedVertex"  (7)

"CycleEdge"の後，"VisitedVertex"か"UnvisitedVertex"が引き起される：

隣接頂点がすでに訪問された場合には，"VisitedVertex"が引き起される：

有向の木において先行頂点が"VisitedVertex"に渡されることを示す：

事象はこのグラフについては全く引き起されない：

無向の木において：

頂点が訪問された後，これはその子供のそれぞれからもう一度訪問を受ける：

有向のCycleGraphにおいて：

無向のCycleGraphにおいて：

有向巡回グラフにおいて：

事象はこのグラフについては全く引き起されない：

格子グラフにおいて：

頂点が訪問された後，これはゼロ回，1回あるいはそれ以上の回数再訪問されることがある：

アプリケーション  (17)

基本のアプリケーション  (10)

単一頂点から行き着くことができる成分を求める：

頂点集合から行き着くことのできる成分をこの成分の和集合として求める：

頂点に行き着くことができる成分を求める：

頂点から行き着くことのできる成分で異なるものをハイライトする：

無向グラフにおける頂点について連結成分を求める：

見付けた成分頂点をハイライトする：

2つの頂点間の最短距離を求める：

2つの頂点間の最短距離を大変な方法で求める：

頂点の訪問について関数を設定する（前に計算された距離は無視する）：

もとの頂点を初期化し，幅優先順でグラフを走査する：

対象における距離を抽出し，GraphDistanceと比べる：

1に最も近い黒い頂点を求める：

グラフ全体を探索する際に発見の数を数える：

各頂点のカウンタと発見を数えるためのイベントハンドラを設定する：

頂点の中には数回見付けられるものもある：

連結成分すべてを計算する：

無向グラフにおいて，BreadthFirstScanは連結成分の頂点すべてをそれぞれ訪れる：

すべての頂点が訪問されるまで手順を繰り返す：

ConnectedComponentsと比較する：

グラフが二部グラフであるかどうかを調べる：

各頂点について"Partition"の一貫した割当てを求めようとする：

各頂点は，その先行頂点における値によって1あるいは-1の値を割り当てられる：

頂点が再び訪問される場合，これは隣接頂点と同じ値を持ってはいけない：

グラフが矛盾を見付けることなく探索できる場合には，これは二部グラフである：

探索の過程を示す  (4)

"FrontierEdge"を使って幅優先探索の木を構築する：

木をハイライトする：

有向グラフでは，"CycleEdge"の辺は「後退辺」あるいは「交差辺」として分類することができる：

木の辺を黒，交代辺を青，交差辺を破線でスタイル付けする：

後退辺は，幅優先木に加えられると，閉路を形成する：

各頂点の時系列において，発見時に点を付け，訪問前から訪問後へ線を引く：

有向の木において事象の時系列を示す：

無向の木において：

有向のCycleGraphにおいて：

無向のCycleGraphにおいて：

有向巡回グラフにおいて：

格子グラフにおいて：

探索中に頂点の状態がどのように変化するかを示す：

発見された頂点を赤，アクティブな頂点を黄色，訪問された頂点を青で色付けし，木ではない辺の色で頂点が"UnvisitedVertex"（赤）あるいは"VisitedVertex"（青）の どちらの呼出しに繋がるのかを示す：

最短経路のアプリケーション  (3)

重みのないグラフで最短経路を求める：

頂点訪問の関数を設定する：

幅優先順でグラフを走査する：

対象頂点から逆方向に経路を再構築する：

FindShortestPathと比べる：

重みのないグラフで最短経路をすべて求める：

頂点訪問の関数を設定する：

原点の特性を初期化し，グラフを幅優先順で走査する：

対象で結果を抽出する：

Zacharyの古典的な空手クラブネットワークにおける媒介中心性：

頂点訪問の関数を設定する：

すべての頂点からの最短経路をすべて考慮する間に"BetweennessCentrality"を累積する：

媒介中心性の累積分布は，2つの点数が際立っていることを示す：

頂点を媒介中心性の順に並べる（1が管理者で34が講師）：

トップ2の頂点をハイライトする：

特性と関係  (4)

頂点は，幅優先順に見付けられる：

有向グラフについては，発見は辺の方向に従う：

開始頂点から行き着くことができる頂点のみが発見される：

各連結成分から開始頂点を選んで，すべての頂点を発見する：

有向グラフについては，辺の方向に従って行き着くことができる頂点のみが発見される：

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

BibTeX

@misc{reference.wolfram_2024_breadthfirstscan, author="Wolfram Research", title="{BreadthFirstScan}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/BreadthFirstScan.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_breadthfirstscan, organization={Wolfram Research}, title={BreadthFirstScan}, year={2015}, url={https://reference.wolfram.com/language/ref/BreadthFirstScan.html}, note=[Accessed: 22-November-2024 ]}