지시 된 그래프에서 사이클을 감지하기위한 최상의 알고리즘

Question

지시 된 그래프 내의 모든 사이클을 감지하기위한 가장 효율적인 알고리즘은 무엇입니까?

실행 해야하는 작업 일정을 나타내는 지시 된 그래프가 있습니다. 이 그래프 내에서 사이클의 오류 사례를 감지하여 주기적 종속성으로 이어집니다.

Answer 1

Tarjan의 강력하게 연결된 구성 요소 알고리즘 가지다 O(|E| + |V|) 시간 복잡성.

다른 알고리즘은 참조하십시오 강력하게 연결된 구성 요소 Wikipedia에서.

Answer 2

이것이 직업 일정이라는 점을 감안할 때, 나는 어느 시점에서 당신이 종류 제안 된 실행 순서로.

이 경우라면 a 토폴로지 정렬 구현은 어쨌든 사이클을 감지 할 수 있습니다. 유닉스 tsort 확실히. 따라서 별도의 단계가 아닌 Tsorting과 동시에 사이클을 감지하는 것이 더 효율적이라고 생각합니다.

따라서 "루프를 가장 효율적으로 감지하는 방법"보다는 "어떻게 가장 효율적으로 tsort"가 될 수 있습니다. 대답은 아마도 "라이브러리 사용"이지만 다음 Wikipedia 기사에서 실패하지 않습니다.

http://en.wikipedia.org/wiki/topological_sorting

하나의 알고리즘에 대한 의사 코드와 Tarjan의 다른 설명에 대한 간단한 설명이 있습니다. 둘 다 가지고 있습니다 O(|V| + |E|) 시간 복잡성.

Answer 3

DFS로 시작하십시오 :주기는 백 에지는 DFS 동안 발견됩니다. 이것은 백색 경로 정리의 결과로 입증되었습니다.

Answer 4

가장 간단한 방법은 그래프의 깊이 첫 번째 트래버스 (DFT)를 수행합니다..

그래프가있는 경우 n 정점, 이것은 a입니다 O(n) 시간 복잡성 알고리즘. 각 정점에서 시작하여 DFT를 수행해야하므로 총 복잡성이됩니다. O(n^2).

당신은 유지해야합니다 현재 깊이의 모든 정점이 포함 된 스택 퍼스트 트래버스, 첫 번째 요소는 루트 노드입니다. DFT 기간 동안 이미 스택에있는 요소를 발견하면 사이클이 있습니다.

Answer 5

내 생각에, 지시 된 그래프에서 사이클을 감지하기위한 가장 이해할 수있는 알고리즘은 그래프 콜로링-조정입니다.

기본적으로 그래프 채색 알고리즘은 그래프를 DFS 방식으로 걸어갑니다 (깊이의 첫 번째 검색은 다른 경로를 탐색하기 전에 경로를 완전히 탐색 함을 의미합니다). 뒷면 가장자리를 찾으면 그래프를 루프를 포함하는 것으로 표시합니다.

그래프 채색 알고리즘에 대한 심층적 인 설명은이 기사를 읽으십시오. http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

또한 JavaScript에서 그래프 채색 구현을 제공합니다. https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Answer 6

노드에 "방문한"속성을 추가 할 수없는 경우 세트 (또는 맵)를 사용하고 이미 세트에 있지 않는 한 세트에 방문한 모든 노드를 추가하십시오. 고유 한 키나 객체의 주소를 "키"로 사용하십시오.

이것은 또한 사용자가 문제를 해결해야 할 때 유용한 순환 종속성의 "루트"노드에 대한 정보를 제공합니다.

또 다른 해결책은 실행할 다음 종속성을 찾는 것입니다. 이를 위해서는 현재 위치와 다음에해야 할 일을 기억할 수있는 스택이 있어야합니다. 실행하기 전에 종속성이 이미이 스택에 있는지 확인하십시오. 그렇다면주기를 찾았습니다.

이것은 O (n*m)의 복잡성이있는 것처럼 보일 수 있지만 스택은 깊이가 매우 제한되어 있고 (n이 작음) "실행 된"플러스로 체크 오프 할 수있는 각 의존성마다 m이 작아 졌다는 것을 기억해야합니다. 잎을 찾았을 때 검색을 중지 할 수 있습니다 (그래서 당신은 절대 모든 노드를 점검해야합니다 -> m도 작습니다).

Metamake에서는 그래프를 목록 목록으로 작성한 다음 자연스럽게 검색 볼륨을 줄여서 실행하면서 모든 노드를 실행하면 모든 노드를 삭제했습니다. 나는 실제로 독립적 인 수표를 실행할 필요가 없었으며, 정상 실행 중에 모든 것이 자동으로 발생했습니다.

"테스트 전용"모드가 필요한 경우 실제 작업의 실행을 비활성화하는 "드라이 런"플래그를 추가하십시오.

Answer 7

다항식 시간에 지시 된 그래프에서 모든 사이클을 찾을 수있는 알고리즘이 없습니다. 지시 된 그래프에는 N 노드가 있고 모든 노드 쌍에는 서로 연결되어있어 완전한 그래프가 있음을 의미합니다. 따라서 이러한 N 노드의 비어 있지 않은 하위 집합은 사이클을 나타내며 2^N-1 수의 서브 세트가 있습니다. 따라서 다항식 시간 알고리즘은 존재하지 않습니다. 따라서 그래프에서 지시 된주기 수를 알려주는 효율적 (스upid) 알고리즘이 있다고 가정하면 먼저 연결된 구성 요소를 찾은 다음 이러한 연결된 구성 요소에 알고리즘을 적용 할 수 있습니다. 사이클은 구성 요소 내에 만 존재하지 않기 때문에 그 사이에 있지 않기 때문입니다.

Answer 8

DFS가 이미 방문한 정점을 가리키는 가장자리를 찾으면 사이클이 있습니다.

Answer 9

레마에 따르면 22.11 Cormen et al., 알고리즘 소개 (CLRS) :

G의 깊이 우선 검색이 뒤쪽 가장자리가없는 경우에만 지시 된 그래프 G는 acyclic입니다.

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

깊이 우선 검색을위한 CLRS의 의사 코드는 다음을 읽습니다.

CLRS 그림 22.4의 예에서 그래프는 두 개의 DFS 트리로 구성됩니다. 하나는 노드로 구성됩니다. 유, V, 엑스, 그리고 와이, 및 다른 노드 w 그리고 지. 각 나무에는 하나의 뒷면 가장자리가 포함되어 있습니다 엑스 에게 V 그리고 또 다른 지 에게 지 (자기 루프).

주요 실현은 DFS-VISIT 이웃을 반복하는 동안 기능 v 의 u, 노드는 GRAY 색깔.

다음 파이썬 코드는 CLRS의 의사 코드를 if 사이클을 감지하는 조항이 추가되었습니다.

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 discovered and 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.

Answer 10

내가하는 방식은 방문한 정점의 수를 계산하여 토폴로지의 종류를하는 것입니다. 해당 숫자가 DAG의 총 정점 수보다 작 으면주기가 있습니다.

Answer 11

SML (필수 프로그래밍) 에서이 문제를 구현했습니다. 다음은 개요입니다. 불충분 또는 경과가 0 인 모든 노드를 찾으십시오. 이러한 노드는 사이클의 일부가 될 수 없습니다 (따라서 제거). 다음으로 이러한 노드에서 들어오는 모든 또는 나가는 가장자리를 제거하십시오. 이 프로세스를 결과 그래프에 재귀 적으로 적용하십시오. 끝에 노드 나 모서리가 남아 있지 않으면 그래프에주기가 없으므로 그렇지 않습니다.

Answer 12

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length 나는이 솔루션이 4 길이에 가장 적합합니다. :)

또한 물리 마법사는 U를해야한다고 말합니다 (v^2). 나는 우리가 O (v)/o (v+e) 만 필요하다고 생각합니다. 그래프가 연결되면 DFS는 모든 노드를 방문합니다. 그래프에 서브 그래프가 연결된 경우이 하위 그래프의 정점에서 DFS를 실행할 때마다 연결된 정점을 찾을 수 있으며 다음 실행에 대해 이들을 고려하지 않아도됩니다. 따라서 각 정점에 대한 실행 가능성이 올바르지 않습니다.

Answer 13

당신이 말했듯이, 당신은 일련의 일자리가 있고, 특정 순서로 실행해야합니다. Topological sort 일정 예약에 필요한 순서 (또는 종속성 문제가 direct acyclic graph). 운영 dfs 목록을 유지하고 목록의 시작 부분에 노드를 추가하고 이미 방문한 노드가 발생한 경우. 그런 다음 주어진 그래프에서 사이클을 찾았습니다.

Answer 14

그래프 가이 속성을 만족시키는 경우

|e| > |v| - 1

그런 다음 그래프는 적어도 사이클에 포함됩니다.