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

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

---

유 방향 그래프 내에서 모든주기를 감지하는 가장 효율적인 알고리즘은 무엇입니까?

실행 해야하는 작업 일정, 작업은 노드이고 종속성은 가장자리라는 방향 그래프가 있습니다. 이 그래프 내에서주기의 오류 사례를 감지하여 주기적 종속성을 유발해야합니다.

---

Tarjan의 강력하게 연결된 컴포넌트 알고리즘 은 O(|E| + |V|)시간이 복잡합니다.

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

---

이것이 작업 일정이라는 것을 감안할 때 언젠가 는 제안 된 실행 순서로 정렬 할 것이라고 생각합니다 .

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

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

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

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

---

DFS로 시작 : DFS 중에 백 에지가 발견 된 경우에만주기가 존재합니다 . 이것은 백색 경로 이론의 결과로 증명됩니다.

---

가장 간단한 방법 은 그래프의 DFT (Depth First Traversal)를 수행하는 것입니다 .

그래프에 n꼭짓점이 있으면 O(n)시간 복잡성 알고리즘입니다. 각 정점에서 시작하여 DFT를 수행해야하므로 전체 복잡성이가됩니다 O(n^2).

현재 깊이 첫 번째 순회에서 모든 정점을 포함 하는 스택 을 유지해야 하며 첫 번째 요소는 루트 노드입니다. DFT 중에 이미 스택에있는 요소를 발견하면 사이클이 발생합니다.

---

내 생각에, 유향 그래프에서 사이클을 감지하는 가장 이해하기 쉬운 알고리즘은 그래프 색 알고리즘입니다.

기본적으로 그래프 채색 알고리즘은 DFS 방식으로 그래프를 이동합니다 (Depth First Search, 즉 다른 경로를 탐색하기 전에 경로를 완전히 탐색 함을 의미 함). 뒤쪽 가장자리를 찾으면 루프가 포함 된 것으로 표시합니다.

그래프 채색 알고리즘에 대한 자세한 설명은 다음 기사를 참조하십시오. http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

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

---

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

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

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

이것이 O (N * M)의 복잡성을 갖는 것처럼 보일 수 있지만 스택의 깊이는 매우 제한적이므로 (N이 작음) "실행"플러스로 확인할 수있는 각 종속성에 따라 M이 작아짐을 기억해야합니다. 당신은 당신이 잎을 발견했을 때 검색을 중지 할 수 있습니다 (따라서 모든 노드를 확인할 필요가 없습니다 -> M도 작습니다).

MetaMake에서는 그래프를 목록의 목록으로 만든 다음 검색 볼륨을 자연스럽게 줄이는 노드를 실행할 때마다 모든 노드를 삭제했습니다. 나는 실제로 독립적 인 검사를 수행 할 필요가 없었습니다. 모든 것이 정상적인 실행 중에 자동으로 발생했습니다.

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

---

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

---

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

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

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

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

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

The key realization is that a back edge is encountered when, in the DFS-VISIT function, while iterating over the neighbors v of u, a node is encountered with the GRAY color.

The following Python code is an adaptation of CLRS' pseudocode with an if clause added which detects cycles:

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)

Note that in this example, the time in CLRS' pseudocode is not captured because we're only interested in detecting cycles. There is also some boilerplate code for building the adjacency list representation of a graph from a list of edges.

When this script is executed, it prints the following output:

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

These are exactly the back edges in the example in CLRS Figure 22.4.

---

I had implemented this problem in sml ( imperative programming) . Here is the outline . Find all the nodes that either have an indegree or outdegree of 0 . Such nodes cannot be part of a cycle ( so remove them ) . Next remove all the incoming or outgoing edges from such nodes. Recursively apply this process to the resulting graph. If at the end you are not left with any node or edge , the graph does not have any cycles , else it has.

---

If DFS finds an edge that points to an already-visited vertex, you have a cycle there.

---

The way I do it is to do a Topological Sort, counting the number of vertices visited. If that number is less than the total number of vertices in the DAG, you have a cycle.

---

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I like this solution the best specially for 4 length:)

Also phys wizard says u have to do O(V^2). I believe that we need only O(V)/O(V+E). If the graph is connected then DFS will visit all nodes. If the graph has connected sub graphs then each time we run a DFS on a vertex of this sub graph we will find the connected vertices and wont have to consider these for the next run of the DFS. Therefore the possibility of running for each vertex is incorrect.

---

As you said, you have set of jobs, it need to be executed in certain order. Topological sort given you required order for scheduling of jobs(or for dependency problems if it is a direct acyclic graph). Run dfs and maintain a list, and start adding node in the beginning of the list, and if you encountered a node which is already visited. Then you found a cycle in given graph.

---

If a graph satisfy this property

|e| > |v| - 1

then the graph contains at least on cycle.

참고 URL : https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph