日本語 Wikipedia の深さ優先探索

説明省略のリンク先に使おうかと読んでみたところ、 日本語 Wikipedia に記載されている while ループ版のアルゴリズムは、 訪問済みチェックを継続に入れる前におこなう方法で、 ゴミ集めなどで使われているやりかたです。 この方法は、 行きがけ順を気にせずスタックをできるだけ伸ばさないことを重視するときに使うことが多いようです。

深さ優先探索 - Wikipedia

function 深さ優先探索(v)
    S ← 空のスタック
    v に訪問済みの印を付ける
    v を S に積む
    while S が空ではない do
        v ← S から取り出す
        v を処理する
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                i を S に積む

一方、 英語版 Wikipedia 記載のアルゴリズムは、 純粋な深さ優先です。 強連結成分分解を含むトポロジカル・ソート順が必要なときは、 こちらを使う方が無難です。

Depth-first search - Wikipedia, the free encyclopedia

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

違いを見たければ、 英語 Wikipedia の Example に図示してあるグラフに対して、 頂点 A から始め、 ただし書きにしたがい、 左の弧を右より優先してアルゴリズムを摘要してみると良いでしょう。

https://en.wikipedia.org/wiki/File:Graph.traversal.example.svg

will visit the nodes in the following order: A, B, D, F, E, C, G

日本語 Wikipediaアルゴリズムの摘要結果は次のように変化します。

A, B, D, F, C, G, E

多くの問題には日本語版でも問題なく利用できるでしょう。 ですが、 深さ優先探索を利用するアルゴリズムによっては、 稀に英語版のような純粋な深さ優先を前提にしているものがあるので、 違いを理解しておいた方がよろしいようで。