algorithm मैं कैसे जांच करूं कि एक निर्देशित ग्राफ विश्वकोश है या नहीं?




theory directed-graph (8)

डीएफएस करते समय कोई पिछला किनारा नहीं होना चाहिए। डीएफएस करते समय पहले से देखे गए नोड्स का ट्रैक रखें, यदि आपको वर्तमान नोड और मौजूदा नोड के बीच किनारे का सामना करना पड़ता है, तो ग्राफ में चक्र होता है।

मैं कैसे जांच करूं कि एक निर्देशित ग्राफ विश्वकोश है या नहीं? और एल्गोरिदम कैसे कहा जाता है? मैं एक संदर्भ की सराहना करता हूं।


समाधान 1 : चक्र जांचने के लिए कन्न एल्गोरिदम । मुख्य विचार: एक कतार बनाए रखें जहां शून्य डिग्री के साथ नोड कतार में जोड़ा जाएगा। फिर कतार खाली होने तक नोड को एक-एक करके छील दें। जांचें कि क्या कोई नोड के किनारे मौजूद हैं या नहीं।

समाधान 2 : मजबूत कनेक्टेड घटक की जांच करने के लिए Tarjan एल्गोरिदम

समाधान 3 : डीएफएस । नोड की वर्तमान स्थिति को टैग करने के लिए पूर्णांक सरणी का उपयोग करें: यानी 0 - इस नोड को पहले नहीं देखा गया है। -1 - इसका मतलब है कि इस नोड का दौरा किया गया है, और इसके बच्चों के नोड्स का दौरा किया जा रहा है। 1 - इसका मतलब है कि इस नोड का दौरा किया गया है, और यह हो गया है। तो यदि डीएफएस करते समय नोड की स्थिति -1 है, तो इसका मतलब है कि एक चक्र अस्तित्व में होना चाहिए।


मुझे पता है कि यह एक पुराना विषय है, लेकिन भविष्य के खोजकर्ताओं के लिए यहां एक सी # कार्यान्वयन है जिसे मैंने बनाया है (कोई दावा नहीं है कि यह सबसे कुशल है!)। यह प्रत्येक नोड की पहचान करने के लिए एक सरल पूर्णांक का उपयोग करने के लिए डिज़ाइन किया गया है। आप इसे सजाने के लिए तैयार कर सकते हैं, हालांकि आपको अपनी नोड ऑब्जेक्ट हैश प्रदान करना पसंद है और ठीक से बराबर है।

बहुत गहरे ग्राफ के लिए यह उच्च ओवरहेड हो सकता है, क्योंकि यह गहराई में प्रत्येक नोड पर एक हैशसेट बनाता है (वे चौड़ाई से अधिक नष्ट हो जाते हैं)।

आप उस नोड को इनपुट करते हैं जिससे आप खोजना चाहते हैं और पथ उस नोड पर ले जाता है।

  • एक रूट रूट नोड वाले ग्राफ़ के लिए आप उस नोड और खाली हैशसेट भेजते हैं
  • एक ग्राफ़ के लिए कई रूट नोड्स होने के कारण आप इसे उन नोड्स पर फ़ोरैच में लपेटते हैं और प्रत्येक पुनरावृत्ति के लिए एक नया खाली हैशसेट पास करते हैं
  • किसी दिए गए नोड के नीचे चक्रों की जांच करते समय, उस नोड को खाली हैशसेट के साथ पास करें

    private bool FindCycle(int node, HashSet<int> path)
    {
    
        if (path.Contains(node))
            return true;
    
        var extendedPath = new HashSet<int>(path) {node};
    
        foreach (var child in GetChildren(node))
        {
            if (FindCycle(child, extendedPath))
                return true;
        }
    
        return false;
    }
    

पुस्तक पर लेम्मा 22.11 Introduction to Algorithms (द्वितीय संस्करण) के Introduction to Algorithms चलता है कि:

एक निर्देशित ग्राफ जी विश्वकोश है यदि केवल और यदि जी की गहराई की पहली खोज कोई पिछली किनारों को उत्पन्न नहीं करती है



ग्राफ़ के चक्र होने पर यह पता लगाने के लिए एक त्वरित कोड है:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

विचार इस तरह है: विज़िट किए गए नोड्स का ट्रैक रखने के लिए एक सरणी के साथ एक सामान्य डीएफएस एल्गोरिदम, और एक अतिरिक्त सरणी जो नोड्स के लिए मार्कर के रूप में कार्य करती है जो वर्तमान नोड को जन्म देती है, ताकि जब भी हम नोड के लिए एक डीएफएस निष्पादित करते हैं हमने मार्कर सरणी में अपने संबंधित आइटम को सत्य के रूप में सेट किया है, ताकि जब कभी पहले से ही नोड का दौरा किया गया हो, हम जांच लें कि मार्कर सरणी में इसकी संबंधित वस्तु सही है या नहीं, अगर यह सच है तो यह नोड्स में से एक है जो स्वयं को (इसलिए एक चक्र), और यह चाल तब भी होती है जब नोड के एक डीएफएस रिटर्न हम अपने संबंधित मार्कर को झूठी पर वापस सेट करते हैं, ताकि अगर हम इसे किसी दूसरे मार्ग से फिर से देख सकें तो हम मूर्ख नहीं होते।


ShuggyCoUk द्वारा दिया गया समाधान अधूरा है क्योंकि यह सभी नोड्स की जांच नहीं कर सकता है।


def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

इसमें टाइमकप्लेक्सिटी ओ (एन + एम) या ओ (एन ^ 2) है


एक सरल गहराई-पहली खोज करना चक्र खोजने के लिए पर्याप्त नहीं है। मौजूदा चक्र के बिना डीएफएस में कई बार नोड पर जाना संभव है। आप कहां से शुरू करते हैं, इस पर निर्भर करते हुए, आप पूरे ग्राफ पर भी नहीं जा सकते हैं।

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

चूंकि रटर प्रिंस बताते हैं, यदि आपका ग्राफ कनेक्ट नहीं है, तो आपको प्रत्येक कनेक्टेड घटक पर खोज दोहराना होगा।

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







directed-acyclic-graphs