Iterative Tiefensuche zur Zykluserkennung in gerichteten Graphen

Question

Ich habe diesen Pseudocode gefunden Wikipedia, und sieht sehr elegant und intuitiv aus:

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

Ich versuche, hierfür eine iterative Version mit 3 Markierungen (UNVISITED, VISITED, PROCESSED) zu schreiben, aber das Fehlen einer Schwanzrekursion stört mich wirklich.

Wie soll ich das angehen?

Answer 1

Mit der gleichen Logik wie der rekursive Algorithmus habe ich dem Stapel a hinzugefügt pos Wert, der die Position des letzten Nachkommens verfolgt, der gerade verarbeitet wird.

Dies war für die „Backtrack“-Schritte des Algorithmus notwendig.

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

Sie könnten den Knoten „Farben“ hinzufügen, ähnlich der Methode, die beispielsweise für rekursives DFS in CLRS verwendet wird.Wenn Sie jeden Knoten instanziieren (vorausgesetzt, es handelt sich um Objekte), geben Sie a ein Farbe Feld, das jeder Knoten zunächst hat node.color $\xleftarrow{}$ Weiß.

Das Folgende ist Ihr Pseudocode geändert von denen ich glaube, dass sie helfen würden:

    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

Die Idee ist, dass alle „unbesuchten“ Knoten zunächst „weiß“ gefärbt sind.Wenn wir dann auf einen Knoten stoßen, besuchen wir ihn und färben ihn beim Erkunden „grau“.Wenn wir mit der Erkundung dieses Knotens fertig sind, färben wir ihn „schwarz“.Wir rufen DFS nur auf Knoten mit „weißer“ Farbe auf.

Auch hinsichtlich der Implementierung könnte man neben dem Stack noch etwas machen L eine Menge und überprüfen Sie einfach die Größe (da Sie wissen, dass nur unterschiedliche Knoten zu dieser Menge hinzugefügt werden). Sobald die Größe der Anzahl der Knoten entspricht, wissen Sie, dass Sie alle Knoten des Diagramms besucht haben, aber als Wenn Sie die Färbung verwenden, wird es irgendwann so sein, dass es keinen Knoten gibt. n so dass n.color == white.