[algorithm] 유 방향 그래프에서 사이클을 감지하기위한 최상의 알고리즘

Cormen 등 의 Lemma 22.11 , 알고리즘 소개 (CLRS) 에 따르면 :

유 방향 그래프 G는 G에 대한 깊이 우선 탐색이 후방 에지를 생성하지 않는 경우에만 비순환 적이다.

이것은 몇 가지 답변에서 언급되었습니다. 여기에서는 CLRS의 22 장을 기반으로하는 코드 예제도 제공합니다. 예제 그래프는 아래와 같습니다.

깊이 우선 검색을위한 CLRS 의사 코드 :

CLRS 그림 22.4의 예에서 그래프는 두 개의 DFS 트리로 구성됩니다. 하나는 노드 u , v , x 및 y 로 구성되고 다른 하나는 노드 w 및 z로 구성 됩니다. 각 트리에는 하나의 뒷면이 있습니다. 하나는 x 에서 v로 , 다른 하나는 z 에서 z로 (자체 루프).

핵심 실현은에 때, 백 에지가 발생한다는 것입니다 DFS-VISIT이웃 반복하면서 기능, v의 u, 노드가 함께 발생 GRAY색상.

다음 파이썬 코드는 if사이클을 감지 하는 절이 추가 된 CLRS 의사 코드의 적응입니다 .

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

이 예에서는 time사이클 감지에만 관심이 있기 때문에 CLRS의 의사 코드는 캡처되지 않습니다. 가장자리 목록에서 그래프의 인접 목록 표현을 빌드하기위한 상용구 코드도 있습니다.

이 스크립트가 실행되면 다음 출력이 인쇄됩니다.

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

이것들은 CLRS의 예에서 정확히 뒤쪽 가장자리입니다 그림 22.4.

---

답변