Primeira pesquisa de profundidade iterativa para detecção de ciclo em gráficos direcionados

Question

Encontrei este pseudocódigo em Wikipédia, e parece muito 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

Estou tentando escrever uma versão iterativa para isso usando 3 marcas (UNVISITED, VISITED, PROCESSED), mas a falta de recursão de cauda realmente me incomoda.

Como devo abordar isso?

Answer 1

Usando a mesma lógica do algoritmo recursivo, adicionei na pilha um pos valor que acompanha a posição do último descendente atualmente em processamento.

Isso foi necessário para as etapas de “retrocesso” do 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

Você pode adicionar "cores" aos nós de forma semelhante ao método feito para DFS recursivo encontrado no CLRS, por exemplo.Ao instanciar cada nó (assumindo que sejam objetos), coloque um cor campo tal que cada nó inicialmente tenha node.color $\xleftarrow{}$ branco.

O seguinte é o seu pseudocódigo modificado que acredito que ajudaria:

    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

A ideia é que todos os nós "não visitados" comecem com a cor "branca".Então, quando encontramos um nó, nós o visitamos e o colorimos de “cinza” enquanto o exploramos.Quando terminamos de explorar este nó, nós o colorimos de “preto”.Chamamos DFS apenas em nós com cor "branca".

Ainda em relação à implementação, além da pilha, você poderia fazer L um conjunto e apenas verifique o tamanho (já que você sabe que apenas nós distintos serão adicionados a este conjunto) e quando o tamanho for igual ao número de nós, você sabe que visitou todos os nós do gráfico, mas como é que se você usar a coloração eventualmente, não haverá nó, n de tal modo que n.color == white.