有向グラフの深さ優先再帰的トラバース

有向グラフGのchildren関数 |G|→Pow(|G|) を、children(x) = {y∈|G| | xからyに向かう辺がある} で定義する。すべてのchildren(x)が全順序集合になっているようなグラフを考える。局所順序グラフと呼びたいが、誤解されそうだから、semifatグラフと呼ぶ。無向グラフに対してfatという概念があり、それに似ているからsemifat。

基点付きのsemifatグラフに関して、ツリーの深さ優先再帰的トラバースと似た方法で頂点をたどれる。ツリーのパスに相当する [x₀, x₁, ..., x_n] という頂点のリストに関して、次の頂点を計算する。ただし、x₀は常に基点（ルートや開始状態）だとする。

次のような約束／記号／概念を使う。

• children(x)はリストだとする。children(x)が空リストのときもある。リストの順番がsemifat構造を定義する。
• Aが頂点のリスト、Xが頂点の集合のとき、A＼X は「AにXの要素が出現すれば、それを取り除いたリスト」の意味。
• x∈children(p) のとき、younger(p, x)は、children(p)のなかでxより若い（順序でより後）の頂点からなるリスト。xが親pの最後の子（末子）のとき younger(p, x)は空リスト。

既にたどった（訪れた）頂点の集合をVisited、[x₀, x₁, ..., x_n] というリストをパスリストと呼ぶことにする。Visitedの初期値は空集合、パスリストの初期値は [基点] 。

手順：

1. パスリストが空のときは、次の頂点は定義されない。終了。
2. 空でないパスリストの最後の頂点x_nをxとする。
3. children(x)＼Visited が空リストでないなら、その最初の頂点が次の頂点。Visitedに現在の頂点を入れ、パスリストに次の頂点をpushして、現在の頂点 := 次の頂点 と更新する。
4. children(x)＼Visited が空リストで、パスリストにx以外の頂点がないなら次の頂点は定義されない。終了。
5. x_n-1があればそれを pとする。
6. children(x)＼Visited が空リストで、younger(p, x)＼Visited が空でないなら、その最初の頂点が次の頂点。Visitedに現在の頂点を入れ、パスリストのpop後に次の頂点をpushして、現在の頂点 := 次の頂点 と更新する。
7. children(x)＼Visited も younger(p, x)＼Visited も空のときは、パスリストをpopして、最初（手順1）からやり直す。