깊이 우선 검색 중에 계통도 그래프의 사이클을 감지하십시오.

Question

말 계보 데이터를 반복적으로로드 중입니다. 일부 잘못된 데이터 세트의 경우 내 재귀가 멈추지 않습니다 ... 이는 데이터에주기가 있기 때문입니다.

반복을 중지하기 위해 이러한주기를 어떻게 찾을 수 있습니까?

모든 "방문한"말을 사용하여 hashTable을 반복적으로 유지하면서 생각했습니다. 그러나 말은 나무에 두 번있을 수 있기 때문에 잘못된 반응을 발견하게됩니다.

일어날 수없는 일은 말은 ITSELF의 할아버지 또는 할아버지 또는 할아버지로 등장한다는 것입니다.

Answer 1

의사 코드 :

void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen) 
{ 
    if(seen.Contains(currentNode)) return; 
    // Or, do whatever needs to be done when a cycle is detected 

    ProcessHorse(currentNode.Horse); // Or whatever processing you need 

    seen.Push(currentNode); 

    foreach(GenTreeNode childNode in currentNode.Nodes) 
    { 
     ProcessTree(childNode, seen); 
    } 

    seen.Pop(); 
} 

기본적인 아이디어는 우리가 이미 내려 현재 노드에가는 길에 본 적이있는 모든 노드의 목록을 유지하는 것입니다; 우리가 이미 통과 한 노드로 되돌아 간다면 우리는 사이클을 형성했다는 것을 알 수 있습니다. (값을 건너 뛰거나해야 할 일을해야합니다)

Answer 2

트리의 루트까지 이어지는 모든 요소의 스택을 유지 관리합니다.

트리를 아래로 내려갈 때마다 스택에서 하위 요소를 검색하십시오. 일치하는 것을 발견하면 루프를 발견 했으므로 그 아이를 건너 뜁니다. 그렇지 않으면 자식을 스택 위로 밀어 넣고 계속 진행합니다. 트리를 뒤로 가져올 때마다 스택에서 요소를 팝하고 버립니다.

은 (족보 데이터의 경우, 트리에서 "아이"노드는 아마도 "부모"노드의 생물학적 부모입니다.)

Answer 3

이를 감지하는 아주 간단한 방법은, 그 제약 조건을 확인하는 것입니다 그 자체 :

내가 말할 수없는 것은 말이 ITSELF의 아버지 또는 할아버지 또는 greatgrandfather로 나타나는 것입니다.

노드를 트리에 삽입 할 때마다 트리가 루트로 이동하여 말이 모든 종류의 부모로 존재하지 않는지 확인하십시오.

속도를 높이기 위해 각 노드에 해시 테이블을 연결할 수 있습니다. 여기서 해시 테이블을 사용하면 이러한 조회의 캐시를 저장할 수 있습니다. 그러면 다음 번에 그 노드 아래에 말을 넣을 때 전체 경로를 검색 할 필요가 없습니다.

Answer 4

해시 테이블 솔루션은 다음과 같은 경우 작동합니다. 말 대신 노드를 추적합니다. 값/말이 이전 노드의 값/말과 같을지라도 새 말을 읽을 때마다 새 노드를 만들 때마다 확인하십시오.

Answer 5

당신은 나무가 아닌 directed acyclic graph을 다루고 있습니다. 말의 자손은 조상이 될 수 없으므로주기가 없어야합니다.

이 사실을 알고 있다면, 지향 비순환 그래프와 관련된 코드 기법을 적용해야합니다.

Answer 6

마지막으로 인터뷰 퀴즈 질문을 적용 할 수있는 경우처럼 들릴 수 있습니다. O (1) 메모리 만 사용하여 링크 된 목록에서주기를 찾으십시오.

이 경우 "연결 목록"은 열거하는 요소의 순서입니다.두 개의 열거자를 사용하고 반 속도로 실행하고 빠른 것이 느린 속도로 실행되면 루프가 생깁니다. 이것은 또한 '본'목록을 확인하는 데 필요한 O (n^2) 시간 대신 O (n) 시간이됩니다. 단점은 일부 노드가 여러 번 처리 된 후에 만 ​​루프에 대해 알아낼 수 있다는 것입니다.

예에서 '반 속도'방법을 쓰기가 더 쉬운 '드롭 마커'방법으로 바꿨습니다.

class GenTreeNode { 
    ... 

    ///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary> 
    private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) { 
     long cur_track_count = 0; 
     long high_track_count = 1; 
     T post = default(T); 
     foreach (var e in sub_enumerable) { 
      yield return e; 
      if (++cur_track_count >= high_track_count) { 
       post = e; 
       high_track_count *= 2; 
       cur_track_count = 0; 
      } else if (object.ReferenceEquals(e, post)) { 
       throw new Exception("Infinite Loop"); 
      } 
     } 
    } 

    ... 

    ///<summary>Enumerates the tree's nodes, assuming no cycles</summary> 
    private IEnumerable<GenTreeNode> tree_nodes_unchecked() { 
     yield return this; 
     foreach (var child in this.nodes) 
      foreach (var e in child.tree_nodes_unchecked()) 
       yield return e; 
    } 
    ///<summary>Enumerates the tree's nodes, checking for cycles</summary> 
    public IEnumerable<GenTreeNode> tree_nodes() 
    { 
     return CheckedEnumerable(tree_nodes_unchecked()); 
    } 

    ... 

    void ProcessTree() { 
     foreach (var node in tree_nodes()) 
      proceess(node); 
    } 
}