Phát hiện chu trình trong biểu đồ phả hệ trong khi tìm kiếm Độ sâu đầu tiên

Question

Tôi đang tải dữ liệu phả hệ ngựa theo cách đệ quy. Đối với một số bộ dữ liệu sai, đệ quy của tôi không bao giờ dừng lại ... và đó là vì có các chu kỳ trong dữ liệu.

Làm cách nào tôi có thể phát hiện các chu kỳ đó để dừng định kỳ?

Tôi đã nghĩ đến việc định kỳ duy trì hashTable với tất cả các con ngựa "đã truy cập". Nhưng điều đó sẽ tìm thấy một số dương tính giả, bởi vì một con ngựa có thể được hai lần trong một cái cây.

Điều không thể xảy ra là một con ngựa xuất hiện như một người cha hoặc ông nội hoặc ông cố của ITSELF.

Answer 1

Pseudo code:

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(); 
} 

Ý tưởng cơ bản là để giữ một danh sách của tất cả các nút mà chúng ta đã nhìn thấy trên đường đi xuống đến nút hiện hành; nếu đã quay lại nút mà chúng tôi đã trải qua, thì bạn biết rằng chúng tôi đã hình thành một chu kỳ (và chúng tôi nên bỏ qua giá trị hoặc thực hiện bất kỳ điều gì cần làm)

Answer 2

Duy trì một chồng tất cả các phần tử dẫn đến gốc cây.

Mỗi khi bạn tiến xuống cây, hãy quét ngăn xếp cho phần tử con. Nếu bạn tìm thấy một trận đấu, thì bạn đã phát hiện ra một vòng lặp và nên bỏ qua đứa trẻ đó. Nếu không, hãy đẩy trẻ vào ngăn xếp và tiếp tục. Bất cứ khi nào bạn backtrack lên cây, pop một phần tử ra khỏi ngăn xếp và loại bỏ.

(Trong trường hợp dữ liệu gia phả, một "đứa trẻ" nút trong cây có lẽ là cha mẹ ruột của nút "cha mẹ".)

Answer 3

Một cách rất đơn giản để phát hiện này, là bằng cách kiểm tra ràng buộc chính nó:

Điều không thể xảy ra là con ngựa xuất hiện với tư cách là cha hoặc ông nội hoặc người tuyệt vời của ITSELF.

Bất cứ khi nào bạn chèn một nút vào cây, di chuyển cây đến gốc để đảm bảo rằng con ngựa không tồn tại dưới dạng bất kỳ loại phụ huynh nào.

Để tăng tốc độ này, bạn có thể kết hợp thẻ bắt đầu bằng # cho mỗi nút, nơi bạn lưu trữ câu trả lời của lần tra cứu đó. Sau đó, bạn không phải tìm kiếm toàn bộ đường dẫn lần sau khi bạn chèn một con ngựa dưới nút đó.

Answer 4

Giải pháp bảng băm của bạn sẽ hoạt động nếu bạn theo dõi các nút thay vì ngựa. Chỉ cần đảm bảo mỗi lần bạn đọc một con ngựa mới, bạn tạo một nút mới ngay cả khi giá trị/con ngựa giống với giá trị/con ngựa của nút trước đó.

Answer 5

Bạn đang xử lý một số directed acyclic graph, không phải là cây. Không nên có bất kỳ chu kỳ nào, vì hậu duệ của một con ngựa cũng không thể là tổ tiên của nó.

Biết điều này, bạn nên áp dụng các kỹ thuật mã cụ thể cho biểu đồ tuần hoàn theo chỉ dẫn.

Answer 6

Điều này giống như trường hợp cuối cùng bạn có thể áp dụng câu hỏi phỏng vấn đó: tìm một chu trình trong danh sách được liên kết chỉ sử dụng bộ nhớ O (1).

Trong trường hợp này, "danh sách được liên kết" của bạn là chuỗi các phần tử bạn liệt kê.Sử dụng hai điều tra viên, chạy một ở tốc độ một nửa, và nếu một nhanh chóng bao giờ chạy vào một chậm sau đó bạn có một vòng lặp. Đây cũng sẽ là thời gian O (n) thay vì thời gian O (n^2) cần thiết để kiểm tra danh sách 'nhìn thấy'. Nhược điểm là bạn chỉ tìm hiểu về vòng lặp sau khi một số nút đã được xử lý nhiều lần.

Trong ví dụ, tôi đã thay thế phương pháp 'nửa tốc độ' bằng phương pháp 'đánh dấu thả' đơn giản hơn để viết.

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); 
    } 
}