C#: Tránh đệ quy vô hạn khi duyệt qua biểu đồ đối tượng

Question

Tôi có biểu đồ đối tượng trong đó mỗi đối tượng con chứa thuộc tính tham chiếu lại đối tượng gốc của nó. Có bất kỳ chiến lược tốt nào để bỏ qua các tham chiếu gốc để tránh đệ quy vô hạn không? Tôi đã xem xét việc thêm thuộc tính [Parent] đặc biệt vào các thuộc tính này hoặc sử dụng một quy ước đặt tên đặc biệt, nhưng có lẽ có một cách tốt hơn.

Answer 1

Nếu vòng lặp có thể được khái quát hóa (bạn có thể có bất kỳ số phần tử nào tạo vòng lặp), bạn có thể theo dõi các đối tượng bạn đã xem trong HashSet và dừng nếu đối tượng đã có trong bộ khi bạn thăm nó. Hoặc thêm cờ vào các đối tượng mà bạn đặt khi bạn truy cập vào nó (nhưng sau đó bạn phải quay lại & bỏ đặt tất cả các cờ khi bạn hoàn tất và chỉ có thể duyệt qua biểu đồ theo một chuỗi đơn tại một thời điểm).

Ngoài ra, nếu vòng lặp sẽ chỉ quay lại phụ huynh, bạn có thể giữ tham chiếu đến cấp độ gốc và không lặp lại các thuộc tính tham chiếu đến nó.

Để đơn giản, nếu bạn biết các tài liệu tham khảo phụ huynh sẽ có một cái tên nào đó, bạn có thể chỉ là không lặp về sở hữu :) rằng

Answer 2

Nếu bạn đang làm một traversal đồ thị, bạn có thể có một "viếng thăm" cờ trên mỗi nút. Điều này đảm bảo rằng bạn không truy cập lại một nút và có thể bị kẹt trong một vòng lặp vô hạn. Tôi tin rằng đây là cách tiêu chuẩn để thực hiện truyền tải đồ thị.

Answer 3

Tôi không chắc chắn những gì bạn đang cố gắng làm ở đây nhưng bạn chỉ có thể duy trì một hashtable với tất cả các nút đã truy cập trước đó khi bạn đang thực hiện tìm kiếm đầu tiên chiều rộng bề rộng của bạn.

Answer 4

Thật trùng hợp; đây là chủ đề của my blog thứ hai tới này. Xem nó để biết thêm chi tiết. Cho đến lúc đó, đây là một số mã để cung cấp cho bạn một ý tưởng về làm thế nào để làm điều này:

static IEnumerable<T> Traversal<T>(
    T item, 
    Func<T, IEnumerable<T>> children) 
{ 
    var seen = new HashSet<T>(); 
    var stack = new Stack<T>(); 
    seen.Add(item); 
    stack.Push(item); 
    yield return item; 
    while(stack.Count > 0) 
    { 
     T current = stack.Pop(); 
     foreach(T newItem in children(current)) 
     { 
      if (!seen.Contains(newItem)) 
      { 
       seen.Add(newItem); 
       stack.Push(newItem); 
       yield return newItem; 
      } 
     } 
    } 
} 

Phương pháp này có hai điều: một mục, và một mối quan hệ sản xuất các thiết lập của tất cả mọi thứ đó là tiếp giáp với mặt hàng đó. Nó tạo ra một chiều ngang đầu tiên theo chiều sâu của việc đóng cửa liên tục và phản xạ của mối quan hệ kề trên mục. Để số lượng mục trong biểu đồ là n và độ sâu tối đa là 1 < = d < = n, giả sử hệ số phân nhánh không bị giới hạn. Thuật toán này sử dụng một stack rõ ràng hơn là đệ quy vì (1) đệ quy trong trường hợp này biến những gì nên là một O (n) thuật toán vào O (nd), đó là sau đó một cái gì đó giữa O (n) và O (n^2), và (2) đệ quy quá mức có thể thổi tung ngăn xếp nếu d lớn hơn vài trăm nút.

Lưu ý rằng việc sử dụng bộ nhớ đỉnh của thuật toán này tất nhiên là O (n + d) = O (n).

Vì vậy, ví dụ:

foreach(Node node in Traversal(myGraph.Root, n => n.Children)) 
    Console.WriteLine(node.Name); 

Make ý nghĩa?

Answer 5

Đây là một vấn đề phổ biến, nhưng cách tiếp cận tốt nhất phụ thuộc vào kịch bản. Một vấn đề nữa là trong nhiều trường hợp nó không phải là một vấn đề thăm cùng một đối tượng hai lần - điều đó không có nghĩa đệ quy - ví dụ, hãy xem xét cây:

A 
=> B 
    => C 
=> D 
    => C 

Điều này có thể có giá trị (nghĩ XmlSerializer , chỉ đơn giản là viết ví dụ C hai lần), vì vậy thường cần phải đẩy/bật các đối tượng trên một ngăn xếp để kiểm tra đệ quy thực sự.Lần cuối cùng tôi triển khai "khách truy cập", tôi đã giữ bộ đếm "chiều sâu" và chỉ cho phép kiểm tra ngăn xếp vượt quá ngưỡng nhất định - nghĩa là hầu hết các cây chỉ cần thực hiện một số ++/--, nhưng không có gì đắt hơn. Bạn có thể thấy cách tiếp cận tôi đã chụp here.

Answer 6

tôi xuất bản một bài giải thích chi tiết với các ví dụ mã thế nào để làm đối tượng traversal bởi phản ánh đệ quy và cũng phát hiện và tránh tham khảo đệ quy để ngăn chặn một đống trên dòng chảy ngoại lệ: https://doguarslan.wordpress.com/2016/10/03/object-graph-traversal-by-recursive-reflection/

Trong ví dụ mà tôi đã làm một sâu đầu tiên traversal bằng cách sử dụng phản xạ đệ quy và tôi duy trì một HashSet của các nút truy cập cho các kiểu tham chiếu. Một điều cần thận trọng là khởi tạo HashSet của bạn bằng trình so sánh tùy chỉnh sử dụng tham chiếu đối tượng để tính toán băm, về cơ bản phương thức GetHashCode() được thực hiện bởi lớp đối tượng cơ sở và không phải bất kỳ phiên bản quá tải nào của GetHashCode() vì nếu các kiểu của các thuộc tính mà bạn vượt qua quá tải phương thức GetHashCode, bạn có thể phát hiện các tham chiếu đệ quy sai và nghĩ rằng bạn đã phát hiện một tham chiếu đệ quy trong thực tế có thể là phiên bản quá tải của GetHashCode tạo ra cùng giá trị băm thông qua một số chẩn đoán và gây nhầm lẫn cho HashSet, tất cả những gì bạn cần phát hiện là kiểm tra xem có bất kỳ con cha mẹ nào ở bất cứ nơi nào trong cây đối tượng trỏ đến cùng một vị trí trong bộ nhớ hay không.