Primera búsqueda iterativa en profundidad para detección de ciclos en gráficos dirigidos

Question

Encontré este pseudocódigo en Wikipedia, y se ve muy elegante e intuitivo:

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

Estoy intentando escribir una versión iterativa para esto usando 3 marcas (NO VISITADO, VISITADO, PROCESADO), pero la falta de recursividad de cola realmente me molesta.

¿Cómo debo abordar esto?

Answer 1

Uso de la misma lógica que el algoritmo recursivo, agregué en la pila un valor pos que realiza un seguimiento de la posición del último descendiente que se procesa actualmente.

Esto fue necesario para los pasos de "backtrack" del 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

Podría agregar "colores" a los nodos de manera similar al método realizado para DFS recursivo que se encuentra en CLRS, por ejemplo.Cuando crea una instancia de cada nodo (suponiendo que sean objetos), coloque un color campo tal que cada nodo inicialmente tiene node.color $\xflecha izquierda{}$ blanco.

El siguiente es su pseudocódigo modificado que creo que ayudaría:

    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

La idea es que todos los nodos "no visitados" comiencen en color "blanco".Luego, cuando encontramos un nodo, lo visitamos y lo coloreamos "gris" mientras lo exploramos.Cuando terminamos de explorar este nodo, lo coloreamos "negro".Solo llamamos a DFS en nodos con color "blanco".

También con respecto a la implementación, además de la pila, podrías hacer L un conjunto y simplemente verifique el tamaño (ya que sabe que solo se agregarán nodos distintos a este conjunto) y una vez que el tamaño sea igual al número de nodos, sabrá que ha visitado todos los nodos del gráfico, pero como es que si usas el color eventualmente se dará el caso de que no haya ningún nodo, n tal que n.color == white.