DepthFirstScan

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

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

詳細詳細

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

例題例題すべて開くすべて閉じる

例 (3)例 (3)

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

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

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=

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

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=
In[3]:=
Click for copyable input
In[4]:=
Click for copyable input
Out[4]=
バージョン 8 の新機能
New to Mathematica? Find your learning path »
Have a question? Ask support »