Profondità iterativa Prima ricerca per il rilevamento del ciclo sui grafici diretti

Question

Ho trovato questo pseudocode su wikipedia , e sembra molto elegante e intuitivo: Sto cercando di scrivere una versione iterativa per questo utilizzo di 3 segni (non visitato, visitato, elaborato), ma la mancanza di ricadure della coda mi infastidisce davvero.

Come dovrei avvicinarsi a questo?

Answer 1

Utilizzando la stessa logica dell'algoritmo ricorsivo, ho aggiunto sullo impilato un valore pos che mantiene la traccia della posizione dell'ultimo discendente attualmente in elaborazione.

Era necessario per i gradini "Backtrack" dell'algoritmo.

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

È possibile aggiungere "colori" ai nodi simili al metodo fatto per DF ricorsive trovati in CLRS, ad esempio. Quando stai istanziare ciascun nodo (supponendo che siano oggetti) metti un campo Color in modo tale che ogni nodo ha inizialmente ha inizialmente node.color $ \ xleftarrow {} $ < Strong> Bianco .

Quanto segue è il tuo pseudocodice modificato che credo che ti aiutino:

    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

.

L'idea è che tutti i nodi "non visitati" iniziano a colorare "bianco". Quindi, quando incontriamo un nodo, lo visitiamo e ci colleghiamo "grigi" mentre lo esplorano. Quando abbiamo finito di esplorare questo nodo, ci coloriamo "nero". Chiamiamo solo DFS sui nodi con colore "bianco".

anche per quanto riguarda l'implementazione, oltre alla pila, è possibile effettuare un gruppo L e semplicemente eseguire un controllo sulla dimensione (dal momento che sai solo i nodi distinti verranno aggiunti a questo set) e una volta che la dimensione è uguale al numero Di nodi sai di aver visitato tutti i nodi del grafico, ma come se usi la colorazione alla fine sarà il caso che non ci sia nodo, n in modo tale che n.color == white.