DepthFirstScan

• DepthFirstScanは，深さ優先順に頂点 s に連結されているグラフ g 内の頂点を訪れる．

• 深さ優先順では，最も最近訪れられた頂点に隣接する頂点が最初に訪れられる．

• DepthFirstScanは，g の頂点リストの最初の頂点から始めて，複数の深さ優先探索を行い，その後まだ訪れていない頂点リストの最初の頂点から順に始めることにより，事実上それぞれの連結成分をスキャンする．

• DepthFirstScanは， が に先行するものであり，が g の頂点リストである木を表すリストを与える．

• 頂点の発見にアクセスを提供する事象：

• "DiscoverVertex"->fd は，開始頂点 s からの距離 d の地点で頂点 u が訪れられた頂点 v から見付けられるとき，を呼び出す．

• "UnvisitedVertex"->fru は，訪れていない頂点 u が訪れた頂点 v からもう一度見付けられる場合に，を呼び出す．

• "VisitedVertex"->frv は，訪れた頂点 u が訪れた頂点 v からもう一度見付けられる場合に，を呼び出す．

• 頂点の訪問へのアクセスを提供する事象：

• "PrevisitVertex"->fs は頂点 u を訪れる前に を呼び出す．

• "PostvisitVertex"->fe は頂点 u を訪れた後に を呼び出す．

• 深さ優先探索の木は，深さ優先探索の際に走査された辺によって生成される木である．

• 訪れた頂点から辺の探査へのアクセスを提供する事象：

• "FrontierEdge"->ffe は，頂点 v が訪れられていて，u がまだ見付けられていない場合の辺 について を呼び出す．これは通常深さ優先探索の木をスキャンする際に便利である．

• "BackEdge"->fbe は，頂点 v が訪れられていて，u がもう見付けられ，深さ優先探索の木において v の祖先である場合に，辺 について を呼び出す．これは通常ループを見付けるのに有益である．

• "ForwardEdge"->gfe は，頂点 v が訪れられていて，u がもう見付けられ，深さ優先探索の木において v の子孫である場合に，辺 について を呼び出す．

• "CrossEdge"->fce は，頂点 v が訪れられていて，u がもう見付けられ，現行の深さ優先探索の木にない場合，あるいは同じ深さ優先探索の木の別の枝にある場合に，辺 について を呼び出す．これは通常複数の深さ優先探索の木を検出するのに有益である．

• 無向グラフについては，呼び出しに使われる辺は無向の辺 であると見なされる．