DepthFirstScan

DepthFirstScan[g,s,{"event1"f1,"event2"f2,…}]

グラフ g の深さ優先探索を頂点 s から始めて行い，"eventi" が起るたびに fiを評価する．

DepthFirstScan[g,{"event1"f1,"event2"f2,…}]

グラフ g 全体の深さ優先探索を行う．

DepthFirstScan[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細

  • DepthFirstScanは，深さ優先探索(DFS)あるいは縦型探索としても知られている．
  • DepthFirstScan[g,s,{…}]は，深さ優先順に頂点 s に連結されているグラフ g 内の頂点を訪れる．
  • 深さ優先順では，最も最近訪れられた頂点に隣接する頂点が最初に訪れられる．
  • DepthFirstScan[g,{…}]は，g の頂点リストの最初の頂点から始めて，複数の深さ優先探索を行い，その後まだ訪れていない頂点リストの最初の頂点から順に始めることにより，事実上それぞれの連結成分をスキャンする．
  • DepthFirstScan[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"深さ優先探索の木の辺
    "BackEdge"深さ優先探索の木の祖先への辺
    "ForwardEdge"深さ優先探索の木の子孫への辺
    "CrossEdge"その他の辺
  • "FrontierEdge"->ffe は，頂点 v が訪れられていて，u がまだ見付けられていない場合の辺 vu について ffe[vu]を呼び出す．これは通常深さ優先探索の木をスキャンする際に便利である．
  • "BackEdge"->fbe は，頂点 v が訪れられていて，u がもう見付けられ，深さ優先探索の木において v の祖先である場合に，辺 vu について fbe[vu]を呼び出す．これは通常ループを見付けるのに有益である．
  • "ForwardEdge"->gfe は，頂点 v が訪れられていて，u がもう見付けられ，深さ優先探索の木において v の子孫である場合に，辺 vu について gfe[vu]を呼び出す．
  • "CrossEdge"->fce は，頂点 v が訪れられていて，u がもう見付けられ，現行の深さ優先探索の木にない場合，あるいは同じ深さ優先探索の木の別の枝にある場合に，辺 vu について fce[vu]を呼び出す．これは通常複数の深さ優先探索の木を検出するのに有益である．
  • 無向グラフについては，呼び出しに使われる辺は無向の辺 vu であるとみなされる．

予備知識

  • DepthFirstScanは，根の頂点から始めて，バックトラックする前にできるだけ深く進む，グラフの走査を行う．探索（頂点の発見，未訪問の頂点の発見，あるいは頂点の再発見）の最中に起る関連の事象それぞれにおいて，ユーザ定義の関数を評価することができる．深さ優先の走査は，1970年代初頭にTarjanとHopcroftが示したように，グラフ理論の多くの問題について結果として線形時間アルゴリズムを返すので，さまざまなグラフ特性を計算するのに有益である．したがって，DepthFirstScanを使うと，カスタムのユーザ定義のグラフ理論アルゴリズムを効率的に実装することができる．適用の例として，連結成分，橋，平面性検定，トポロジカル整列が挙げられる．
  • 深さ優先の順序では，最後に訪れられた頂点の近隣頂点が最初に訪れられる．深さ優先探索は，グラフのすべての頂点と辺を，あるいは指定された頂点から始まる頂点と辺だけを検索あるいは訪問するために使える．
  • 深さ優先探索(DFS)は，バックトラック法または縦型探索とも呼ばれる．フランスの数学者であるCharles Pierre Trémauxが，迷路を解く方法の一つとして，19世紀にはじめて深さ優先探索の1種について研究した．
  • BreadthFirstScanは，根の頂点から始めて，すべての近隣頂点を調べ，調べた近隣頂点の近隣頂点を訪れ，そのまた近隣頂点を訪れるという風に続ける，類似の横断アルゴリズムである．

例題

例  (3)

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

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

頂点が訪れられた順を示すラベルを加える：

Wolfram Research (2010), DepthFirstScan, Wolfram言語関数， https://reference.wolfram.com/language/ref/DepthFirstScan.html （2015年に更新）.

テキスト

Wolfram Research (2010), DepthFirstScan, Wolfram言語関数， https://reference.wolfram.com/language/ref/DepthFirstScan.html （2015年に更新）.

CMS

Wolfram Language. 2010. "DepthFirstScan." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/DepthFirstScan.html.

APA

Wolfram Language. (2010). DepthFirstScan. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/DepthFirstScan.html

BibTeX

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

BibLaTeX

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