गहराई-पहली खोज

Question

के दौरान वंशावली ग्राफ में चक्रों का पता लगाएं मैं घोड़े वंशावली डेटा को दोबारा लोड कर रहा हूं। डेटा के कुछ गलत सेट के लिए मेरा रिकर्सन कभी नहीं रुकता है ... और ऐसा इसलिए है क्योंकि डेटा में चक्र हैं।

आवर्ती रोकने के लिए मैं उन चक्रों का पता कैसे लगा सकता हूं?

मैंने सोचा कि आवर्ती सभी "विज़िट" घोड़ों के साथ हैशटेबल बनाए रखने के बारे में सोचा था। लेकिन कुछ झूठे सकारात्मक पाएंगे, क्योंकि एक घोड़ा पेड़ में दो बार हो सकता है।

ऐसा नहीं हो सकता कि घोड़ा पिता या दादा या आईटीएसईएलएफ के महान दादा के रूप में दिखाई देता है।

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

इस का पता लगाने के लिए एक बहुत ही आसान तरीका है कि बाधा की जाँच करके है स्वयं:

क्या खुशी नहीं हो सकती है कि एक घोड़ा पिता या दादा या आईटीएसईएलएफ के महानगर के रूप में दिखाई देता है।

जब भी आप अपने पेड़ में एक नोड डालें, यह सुनिश्चित करें कि घोड़ा माता पिता के किसी भी प्रकार के रूप में मौजूद नहीं है बनाने के लिए रूट करने के लिए पेड़ बढ़ावा देते हैं।

इसे गति देने के लिए, आप प्रत्येक नोड में हैशटेबल को जोड़ सकते हैं, जहां आप इस तरह के लुकअप का जवाब कैश करते हैं। अगली बार जब आप उस नोड के नीचे घोड़ा डालते हैं तो आपको पूरे पथ को खोजने की ज़रूरत नहीं है।

Answer 4

आपके हैश टेबल समाधान को काम करना चाहिए यदि आप घोड़ों की बजाय नोड्स का ट्रैक रखते हैं। बस सुनिश्चित करें कि हर बार जब आप एक नया घोड़ा पढ़ते हैं तो आप एक नया नोड बनाते हैं, भले ही मूल्य/घोड़ा पिछले नोड के मूल्य/घोड़े जैसा ही हो।

Answer 5

आप एक पेड़ नहीं, directed acyclic graph से निपट रहे हैं। कोई चक्र नहीं होना चाहिए, क्योंकि घोड़े के वंशज भी अपने पूर्वजों के रूप में नहीं हो सकते हैं।

यह जानकर, आपको निर्देशित विश्वकोश ग्राफ के लिए विशिष्ट कोड तकनीक लागू करनी चाहिए।

Answer 6

यह एक ऐसे मामले की तरह लगता है जहां आप आखिरकार साक्षात्कार ट्रिविया प्रश्न लागू कर सकते हैं: केवल ओ (1) मेमोरी का उपयोग करके एक लिंक्ड सूची में एक चक्र खोजें।

इस मामले में आपकी "लिंक की गई सूची" आपके द्वारा गणना किए गए तत्वों का अनुक्रम है।दो गणक का प्रयोग करें, आधा गति पर एक चलाएं, और यदि तेज़ व्यक्ति धीमी गति से चलता है तो आपके पास लूप होता है। यह 'देखी गई' सूची की जांच के लिए आवश्यक ओ (एन^2) समय के बजाय ओ (एन) समय भी होगा। कुछ नोड्स को कई बार संसाधित करने के बाद आप केवल लूप के बारे में पता लगाते हैं।

उदाहरण में मैं सरल करने के लिए लिखने के 'ड्रॉप मार्कर' विधि के साथ 'आधा गति' विधि से बदल दिया है।

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