एक निर्देशित ग्राफ में चक्र का पता लगाने के लिए सर्वश्रेष्ठ एल्गोरिदम

Tarjan's strongly connected components algorithm has O(|E| + |V|) time complexity.

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

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

यह आपको चक्रीय निर्भरता के "रूट" नोड के बारे में जानकारी भी देता है जो उपयोगकर्ता को समस्या को ठीक करने के लिए आसान होगा।

एक और समाधान निष्पादित करने के लिए अगली निर्भरता को खोजने का प्रयास करना है। इसके लिए, आपके पास कुछ ढेर होना चाहिए जहां आप याद कर सकते हैं कि आप कहां हैं और आपको आगे क्या करना है। जांचें कि इसे निष्पादित करने से पहले इस स्टैक पर निर्भरता पहले से ही है या नहीं। यदि ऐसा है, तो आपको एक चक्र मिला है।

While this might seem to have a complexity of O(N*M) you must remember that the stack has a very limited depth (so N is small) and that M becomes smaller with each dependency that you can check off as "executed" plus you can stop the search when you found a leaf (so you never have to check every node -> M will be small, too).

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

यदि आपको "केवल परीक्षण" मोड की आवश्यकता है, तो बस "सूखी दौड़" ध्वज जोड़ें जो वास्तविक नौकरियों के निष्पादन को अक्षम करता है।

जैसा कि आपने कहा था, आपने नौकरियों का सेट किया है, इसे निश्चित क्रम में निष्पादित करने की आवश्यकता है। <कोड> टॉपोलॉजिकल सॉर्ट आपको नौकरियों के शेड्यूलिंग के लिए आवश्यक आदेश दिया गया है (या निर्भरता समस्याओं के लिए यदि यह प्रत्यक्ष आकाशीय ग्राफ है)। dfs चलाएं और एक सूची बनाए रखें, और सूची की शुरुआत में नोड जोड़ने शुरू करें, और यदि आपको पहले से देखा गया नोड का सामना करना पड़ा। फिर आपको दिए गए ग्राफ में एक चक्र मिला।

यह देखते हुए कि यह नौकरियों का एक कार्यक्रम है, मुझे संदेह है कि किसी बिंदु पर आप निष्पादन के प्रस्तावित आदेश में क्रमबद्ध करें जा रहे हैं।

यदि ऐसा है, तो किसी भी मामले में एक स्थलीय क्रम कार्यान्वयन हो सकता है चक्र का पता लगाएं। यूनिक्स <कोड> tsort निश्चित रूप से करता है। मुझे लगता है कि यह संभावना है कि एक अलग चरण के बजाय, एक ही समय में चक्रों को पहचानने के लिए चक्रों का पता लगाने के लिए यह अधिक कुशल है।

तो प्रश्न "मैं सबसे कुशलतापूर्वक लूप का पता कैसे लगा सकता हूं" के बजाय, "मैं सबसे कुशलतापूर्वक कैसे छोटा करूं" बन सकता हूं। जिस पर उत्तर शायद "लाइब्रेरी का उपयोग करें" है, लेकिन निम्नलिखित विकिपीडिया लेख में विफल रहा है:

http://en.wikipedia.org/wiki/Topological_sorting

एक एल्गोरिदम के लिए छद्म कोड है, और तारजन से दूसरे का एक संक्षिप्त विवरण है। दोनों में ओ (| वी | + | ई |) समय जटिलता है।

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

यदि कोई ग्राफ इस संपत्ति को संतुष्ट करता है

|e| > |v| - 1

तो ग्राफ में कम से कम चक्र पर होता है।

डीएफएस के साथ शुरू करें: एक चक्र मौजूद है यदि केवल और यदि बैक-एज डीएफएस के दौरान खोजा जाता है । यह सफेद-पथ थियोरम के परिणामस्वरूप साबित होता है।

मैंने इस समस्या को एसएमएल (अनिवार्य प्रोग्रामिंग) में लागू किया था। रूपरेखा यहाँ है। उन सभी नोड्स को ढूंढें जिनके पास या तो 0 से जुड़ी या बहिर्वाह है। ऐसे नोड्स एक चक्र का हिस्सा नहीं हो सकते हैं (इसलिए उन्हें हटा दें)। इसके बाद ऐसे नोड्स से आने वाले या आउटगोइंग किनारों को हटा दें। परिणामस्वरूप ग्राफ को इस प्रक्रिया को पुन: लागू करें। यदि अंत में आप किसी भी नोड या किनारे से नहीं छोड़े जाते हैं, तो ग्राफ में कोई चक्र नहीं होता है, अन्यथा इसमें होता है।

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I like this solution the best specially for 4 length:)

इसके अलावा भौतिक जादूगर का कहना है कि आपको ओ (वी ^ 2) करना है। मेरा मानना ​​है कि हमें केवल ओ (वी)/ओ (वी + ई) की आवश्यकता है। यदि ग्राफ जुड़ा हुआ है तो डीएफएस सभी नोड्स पर जायेगा। यदि ग्राफ़ ने उप ग्राफ को कनेक्ट किया है तो हर बार जब हम इस उप ग्राफ के वर्टेक्स पर डीएफएस चलाते हैं तो हमें कनेक्टेड वर्टिस मिलेंगे और इन्हें डीएफएस के अगले भाग के लिए नहीं माना जाएगा। इसलिए प्रत्येक चरम के लिए दौड़ने की संभावना गलत है।

कोई एल्गोरिदम नहीं है जो बहुपद समय में निर्देशित ग्राफ में सभी चक्रों को पा सकता है। मान लीजिए, निर्देशित ग्राफ में एन नोड्स हैं और नोड्स की प्रत्येक जोड़ी में एक-दूसरे से कनेक्शन हैं जिसका अर्थ है कि आपके पास एक पूर्ण ग्राफ है। इसलिए इन एन नोड्स का कोई भी रिक्त सबसेट एक चक्र इंगित करता है और ऐसे सबसेट्स की 2 ^ एन -1 संख्या होती है। तो कोई बहुपद समय एल्गोरिदम मौजूद नहीं है।     तो मान लीजिए कि आपके पास एक कुशल (गैर-बेवकूफ) एल्गोरिदम है जो आपको ग्राफ में निर्देशित चक्रों की संख्या बता सकता है, तो आप पहले जुड़े हुए घटकों को ढूंढ सकते हैं, फिर इन कनेक्टेड घटकों पर अपना एल्गोरिदम लागू कर सकते हैं। चूंकि चक्र केवल घटकों के भीतर मौजूद हैं और उनके बीच नहीं।

यदि डीएफएस को एक किनारे मिलती है जो पहले से देखे गए वर्टेक्स को इंगित करती है, तो आपके पास एक चक्र होता है।

मेरी राय में, निर्देशित ग्राफ में चक्र का पता लगाने के लिए सबसे समझने योग्य एल्गोरिदम ग्राफ-रंग-एल्गोरिदम है।

असल में, ग्राफ रंग एल्गोरिदम ग्राफ़ को डीएफएस तरीके से चलाता है (गहराई पहली खोज, जिसका अर्थ है कि यह किसी अन्य पथ की खोज करने से पहले पूरी तरह से पथ की खोज करता है)। जब यह पिछला किनारा पाता है, तो यह ग्राफ को लूप के रूप में चिह्नित करता है।

For an in depth explanation of the graph coloring algorithm, please read this article: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Also, I provide an implementation of graph coloring in JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

//this is better solution in java- 

`

class Package{
    private List dep;
    private String name;
    boolean visited;
    List getDependencies(){
        return this.dep;
    }
    String getName(){}


     public void getBuildOrder(Package p){
         p.visited=true;
         if(p.getDependencies.size()==0) syso(p.getName());
        for( Package p1 : p.getDependencies){
            if(p1.visited) {
                syso("cyclic dependency");
                return;
            }
            getBuildOrder(p1);

        }

    }
     main(){
         Package p = new Package();
        //this p  i having all infor
         getBuildOrder(p);
     }
 }


`