유향 그래프가 순환하는지 감지하는 방법은 무엇입니까?

Question

유향 그래프가 순환하는지 어떻게 감지 할 수 있습니까? 폭 넓은 첫 번째 검색을 사용한다고 생각했지만 잘 모르겠습니다. 어떤 아이디어?

Answer 1

일반적으로 깊이 우선 검색이 대신 사용됩니다. BFS를 쉽게 적용 할 수 있는지 모르겠습니다.

는 DFS에서 스패닝 트리가 방문의 순서로 내장되어 있습니다. 트리 내의 노드의 조상 (ancestor)이 방문되면 (즉, 후방 에지가 생성되면), 사이클을 검출한다.

자세한 내용은 http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf을 참조하십시오.

Answer 2

또 다른 간단한 해결책은 마크 앤드 스위프 방식입니다. 기본적으로 트리의 각 노드에 대해 "방문한"것으로 플래그를 지정한 다음 해당 노드로 이동합니다. "visted"플래그가 설정된 노드가 보이면 사이클이 있음을 알 수 있습니다. 는 "방문"비트를 포함하도록 수정하는 그래프 불가능한 경우

는 노드 포인터들의 세트 대신에 사용될 수있다. 방문한 노드에 플래그를 지정하려면 포인터를 세트에 놓습니다. 포인터가 이미 세트에 있으면 사이클이 있습니다.

Answer 3

당신이 정말로 필요한 것은, 저는 믿습니다, 것과 같은 위상 정렬 알고리즘은 여기에 설명 된 경우 : 방향 그래프가 사이클을 가지고

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

경우 알고리즘은 실패합니다.

코멘트가/I가 감독 그래프에 존재하지 않고 Y 노드에 노드 X에서 얻기 위해 하나 개 이상의 방법이있을 수 있다는 사실을 누락하는 것 지금까지 본 적이 있다고 응답 어떤 (감독) 그래프에서 순환합니다.

Answer 4

접근 방식 : 1
레벨을 지정하면주기를 감지 할 수 없습니다. 예 : 아래 그래프를 고려하십시오. DFS를 시작하면 방문한 노드에 레벨 번호를 지정하기 시작합니다 (루트 A (B, C) B-> D-> (E, F) E, F-> (G) E-> = 0). node = parent + 1의 레벨 번호. A = 0, B = 1, D = 2, F = 3, G = 4이면 재귀가 D에 도달하므로 E = 3이됩니다. G에 대한 마크 레벨은 이미 E보다 강하지 않습니다. 이제 E도 D에 가장자리가 있습니다. 따라서 레벨 화는 D가 4의 레벨을 가져야한다고 말합니다. 그러나 D에는 이미 "하위 레벨"이 할당되어 있습니다 따라서 하위 레벨 번호가 이미 설정된 DFS를 수행하면서 노드에 레벨 번호를 지정하려고하면 방향 그래프에 사이클이있는 것을 알 수 있습니다.

접근 2 :
3 가지 색상을 사용하십시오. 흰색, 회색, 검은 색. DFS를 실행하면 흰색 노드는 회색으로 표시되고 재귀가 펼쳐질 때 회색 노드가 검정색으로 표시됩니다 (모든 자식이 처리됨). 그렇지 않으면 모든 아이들이 아직 처리되지 않았고주기가 회색 노드에 도달했습니다. 예 : 위의 모든 직접 시작 그래프. 색상 A, B, D, F, G는 흰색 회색으로 표시됩니다. G는 잎이기 때문에 모든 아이들은 회색으로 그레이를 색칠했습니다. 재귀는 F (모두 처리 된 어린이)에게 검은 색으로 펼쳐집니다. 이제 당신은 D에 도달하고, D에는 처리되지 않은 아이들이 있습니다. 따라서 색상 E 회색, G는 이미 검정색으로되어 있으므로 더 내려 가지 마십시오. 또한 E는 D에 대해 가장자리가 있으므로 D (D 여전히 회색)를 처리하는 동안 D (회색 노드)로 다시 돌아가는 것을 발견하면주기가 감지됩니다.

Answer 5

주어진 그래프에 대한 위상 정렬을 테스트하면 솔루션으로 연결됩니다. topsort에 대한 알고리즘, 즉 에지가 항상 한 방향으로 전달되어야한다면 그래프에 사이클이 있음을 의미합니다.어떤 경로가 순환 경우

Answer 6

사용 DFS는 검색 할

class Node<T> { T value; List<Node<T>> adjacent; } 

class Graph<T>{ 

    List<Node<T>> nodes; 

    public boolean isCyclicRec() 
    { 

     for (Node<T> node : nodes) 
     { 
      Set<Node<T>> initPath = new HashSet<>(); 
      if (isCyclicRec(node, initPath)) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 

    private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path) 
    { 
     if (path.contains(currNode)) 
     { 
     return true; 
     } 
     else 
     { 
     path.add(currNode); 
     for (Node<T> node : currNode.adjacent) 
     { 
      if (isCyclicRec(node, path)) 
      { 
       return true; 
      } 
      else 
      { 
       path.remove(node); 
      } 
     } 
     } 
     return false; 
    } 

의