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




theory directed-graph (6)

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


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) है


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

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

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

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


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


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

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

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

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

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

यहाँ छील के पत्ते नोड एल्गोरिदम के छिद्र कार्यान्वयन है

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end

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

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

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





directed-acyclic-graphs