유향 그래프에서 주기 감지를 위한 반복적 깊이 우선 검색

Question

나는이 의사 코드를 찾았습니다 위키피디아, 매우 우아하고 직관적으로 보입니다.

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가지 표시(UNVISITED, VISITED, PROCESSED)를 사용하여 이에 대한 반복 버전을 작성하려고 시도하고 있지만 꼬리 재귀가 부족하여 정말 귀찮습니다.

이 문제에 어떻게 접근해야 하나요?

Answer 1

동일한 논리를 재귀 알고리즘으로 사용하면 현재 처리중인 마지막 자손의 위치를 추적하는 PeneraCodiceTag 코드 값을 추가했습니다.

이는 알고리즘의 "BackTrack"단계에 필요했습니다.

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

예를 들어 CLRS에 있는 재귀 DFS에 대해 수행한 방법과 유사하게 노드에 "색상"을 추가할 수 있습니다.각 노드를 인스턴스화할 때(객체라고 가정) 색상 모든 노드가 처음에 node.color $\x왼쪽화살표{}$ 하얀색.

다음은 의사 코드입니다 수정됨 내가 도움이 될 것이라고 믿는 것:

    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를 호출합니다.

또한 구현과 관련하여 스택 외에도 다음을 만들 수 있습니다. L 세트를 만들고 크기를 확인하고(고유한 노드만 이 세트에 추가된다는 것을 알고 있으므로) 크기가 알고 있는 노드 수와 같으면 그래프의 모든 노드를 방문한 것입니다. 컬러링을 사용하면 결국 노드가 없는 경우가 되지만, n 그렇게 n.color == white.