BreadthFirstScan

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

BreadthFirstScan[g, {"event1"->f1, "event2"->f2, ...}]
グラフ g 全体の幅優先探索を行う. 

詳細詳細

  • BreadthFirstScan[g, s, {...}]は,幅優先順に頂点 s に連結されているグラフ g 内の頂点を訪れる.
  • 幅優先順では,現在訪れられている頂点に隣接した頂点すべてがまず訪れられる.
  • BreadthFirstScan[g, {...}]は,g の頂点リストの最初の頂点から始めて,複数の幅優先探索を行い,その後まだ訪れていない頂点リストの最初の頂点から始めることにより,事実上それぞれの連結成分を探索する.
  • BreadthFirstScan[g, ...]は, に先行するものであり,g の頂点リストである木を表すリストを与える.
  • 頂点の発見にアクセスを提供する事象:
  • "DiscoverVertex"いつ頂点が見付けられるか
    "UnvisitedVertex"いつ訪れていない頂点がもう一度見付けられるか
    "VisitedVertex"いつ訪れた頂点がもう一度見付けられるか
  • "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 がもう見付けられた場合の辺 について を呼び出す.通常幅優先探索の木にない閉路や辺を見付けるのに便利である.
  • 無向グラフについては,呼び出しに使われる辺は無向の辺 であると見なされる.
バージョン 8 の新機能
New to Mathematica? Find your learning path »
Have a question? Ask support »