反復深さ優先探索のためのサイクルの検出に向グラフ

Question

この擬似コードに Wikipedia, とも優雅に見え、楽しく直感的

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

って、繰り返しこのバージョン3マーク（未訪問、訪問、また加工）ですが、不足尾再帰本当に面倒だった。

いつ、どのようにアプローチす。

Answer 1

再帰的アルゴリズムと同じ論理を使用して、私は現在処理中の最後の子孫の位置を追跡するpos値をスタックに追加します。

アルゴリズムの「バックトラック」ステップに必要でした。

from typing import List

UNDISCOVERED = -1
DISCOVERED = 0
PROCESSED = 1


def is_acyclic(graph: List[list], vertex_count: int) -> bool:
    state = [UNDISCOVERED] * vertex_count
    for vertex in range(vertex_count):
        if not dfs(graph, vertex, state):
            return False

    return True


def dfs(graph: List[list], v: int, state: list) -> bool:
    stack = [(v, 0)]
    while stack:
        curr, pos = stack[-1]
        if state[curr] == PROCESSED:
            stack.pop()
            continue
        if state[curr] == DISCOVERED and pos == 0:
            return False
        if pos == 0:
            state[curr] = DISCOVERED

        for i in range(pos, len(graph[curr])):
            stack[-1] = curr, pos + 1
            descendant = graph[curr][i]
            stack.append((descendant, 0))
            break
        else:
            state[curr] = PROCESSED

    return True

.

Answer 2

として追加できる"色"のノードと同様の方法で再帰的DFSからCLRSます。ときのインスタンスを生成の各ノードとそのオブジェクト）着 色 分野などの全てのノードを初期 node.color $\xleftarrow{}$ 白.

以下のお擬似コード 修正 ると思っていう:

    L ← Empty list of all nodes, where node.color ← black (once placed here)
    while exists nodes such that node.color is white do
    select a node n such that n.color is white
    visit(n)

function visit(node n)
    if n.color is black then:
        return
    if n.color is gray then:
        stop   (back edge is found indicates cycle exists)

    mark n.color as gray

    for each node m with an edge from n to m do
        visit(m)

    mark n.color as black
    add n to head of L

のアイデアはすべて"未訪問"ノードを開始色の"白".そこから出会いのノードを訪問しています色で"グレー"を探求します。た場合の探索を行い、このノードした色が"黒"。してのみお電話でDFSノード"white"カラーです。

ものに関する実施のほか、スタックが L セットなのにチェックのサイズ（かんのみ異なるノードを取得しますセット)のサイズに等しい数のノードから取り寄せた選りすぐりのも訪れたすべてのノードのグラフをスタートしましたが、ご利用の場合の着色がでる場合がございますのでないノード n その n.color == white.