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

निर्देशित ग्राफ के भीतर सभी चक्रों का पता लगाने के लिए सबसे कुशल एल्गोरिदम क्या है?

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

0
@ हेशहैसिन, यदि आप पहले से देखे गए नोड पर जाते हैं, तो इसका मतलब यह नहीं है कि एक लूप है। कृपया मेरी टिप्पणी पढ़ें cs.stackexchange.com/questions/9676/…
जोड़ा लेखक Maksim Dmitriev, स्रोत
सभी चक्रों का पता लगाना बेहतर होगा ताकि चेक, फिक्स, चेक, फिक्स इत्यादि के बजाए उन्हें एक बार में ठीक किया जा सके।
जोड़ा लेखक Peauters, स्रोत
आप कहते हैं कि आप सभी चक्रों का पता लगाना चाहते हैं, लेकिन आपके उपयोग-मामले से पता चलता है कि यह पता लगाने के लिए पर्याप्त होगा कि क्या कोई चक्र है या नहीं।
जोड़ा लेखक Steve Jessop, स्रोत
आपको डोनाल्ड बी जॉनसन द्वारा "निर्देशित ग्राफ के सभी प्राथमिक सर्किट ढूंढना" पेपर पढ़ना चाहिए। यह केवल प्राथमिक सर्किट पाएगा, लेकिन यह आपके मामले के लिए पर्याप्त होना चाहिए। और यहां उपयोग करने के लिए तैयार इस एल्गोरिदम का मेरा जावा कार्यान्वयन है: github.com/1123/johnson
जोड़ा लेखक user152468, स्रोत
जोड़ा लेखक ARJUN, स्रोत
एल्गोरिदम के लिए अतिरिक्त संशोधन के साथ चलाएं डीएफएस: आपके द्वारा देखे गए प्रत्येक नोड को चिह्नित करें। यदि आप पहले से देखे गए नोड पर जाते हैं, तो आपके पास एक कण है। जब आप किसी पथ से पीछे हट जाते हैं, तो नोड्स को अनमार्क करें।
जोड़ा लेखक Hesham Yassin, स्रोत

13 उत्तर

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

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

0
जोड़ा
(ग्राफ में सभी दृढ़ता से जुड़े घटक)! = (ग्राफ में सभी चक्र)
जोड़ा लेखक optimusfrenk, स्रोत
धन्यवाद अकु, यह काम करना चाहिए और इसका मतलब यह भी होगा कि मैं इस मुद्दे के कारण उप ग्राफ दिखा सकता हूं।
जोड़ा लेखक Peauters, स्रोत
Pleasre केवल लिंक जवाब से बचें।
जोड़ा लेखक Adam Arold, स्रोत
@ सेड्रिक राइट, सीधे नहीं। यह तारजन के एल्गोरिदम में कोई दोष नहीं है, लेकिन इस सवाल के लिए इसका उपयोग किस तरह किया जाता है। तारजन सीधे चक्र नहीं ढूंढता है, यह दृढ़ता से जुड़े घटक पाता है। बेशक, 1 से अधिक आकार वाले किसी भी एससीसी एक चक्र का तात्पर्य है। गैर चक्रीय घटकों के पास एक सिंगलटन एससीसी है। समस्या यह है कि एक स्व-लूप स्वयं भी एक एससीसी में जायेगा। इसलिए आपको स्वयं-लूप के लिए एक अलग जांच की आवश्यकता है, जो कि बहुत छोटा है।
जोड़ा लेखक mgiuca, स्रोत
जैसा कि पीटर ने नोट किया है, दृढ़ता से जुड़े घटक चक्र के बराबर नहीं हैं, लेकिन ग्राफ के भीतर कुशलतापूर्वक चक्र खोजने में मदद कर सकते हैं। चक्र खोजने के लिए, "डोनाल्ड बी जॉनसन द्वारा निर्देशित ग्राफ के सभी प्राथमिक चक्रों को ढूंढना, और जावा में मेरा कार्यान्वयन" पेपर देखें: github.com/1123/johnson
जोड़ा लेखक user152468, स्रोत
दृढ़ता से जुड़े घटकों को ढूंढने से ग्राफ़ में मौजूद चक्रों के बारे में आपको क्या पता चलता है?
जोड़ा लेखक Peter, स्रोत
हो सकता है कि कोई पुष्टि कर सके लेकिन Tarjan एल्गोरिदम नोड्स के चक्रों का समर्थन नहीं करता है, जैसे ए-> ए।
जोड़ा लेखक Cédric Guillemette, स्रोत
विकिपीडिया से: "यदि प्रत्येक दृढ़ता से जुड़े घटक को एक कशेरुक से अनुबंधित किया जाता है, तो परिणामी ग्राफ एक निर्देशित विश्वकोश ग्राफ होता है, जी का घनत्व एक निर्देशित ग्राफ विश्वकोश होता है और केवल तभी होता है जब उसके एक से अधिक वर्टेक्स के साथ कोई दृढ़ता से जुड़े उपग्राफ नहीं होते , क्योंकि एक निर्देशित चक्र दृढ़ता से जुड़ा हुआ है और प्रत्येक नॉनट्रिविअल दृढ़ता से जुड़े घटक में कम से कम एक निर्देशित चक्र होता है। "
जोड़ा लेखक João Almeida, स्रोत
@ अकु: एक तीन रंग डीएफएस में एक ही रनटाइम <कोड> ओ (| ई | + | वी |) है। सफेद (कभी नहीं देखा गया) का उपयोग करके, ग्रे (वर्तमान नोड का दौरा किया जाता है लेकिन सभी पहुंचने योग्य नोड्स अभी तक नहीं देखे जाते हैं) और काला (सभी पहुंचने योग्य नोड्स को वर्तमान के साथ देखा जाता है) रंग कोडिंग, यदि एक ग्रे नोड को एक और ग्रे नोड पाता है तो हम ' एक चक्र है [कॉर्मन की एल्गोरिदम पुस्तक में हमारे पास बहुत कुछ है]। आश्चर्य है कि 'तारजन के एल्गोरिदम' का इस तरह के डीएफएस पर कोई फायदा है !!
जोड़ा लेखक KGhatak, स्रोत

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

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

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

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).

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

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

0
जोड़ा
कृपया डाउनवोट के लिए कारण?
जोड़ा लेखक Gnark, स्रोत

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

0
जोड़ा

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

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

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

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

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

0
जोड़ा

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

0
जोड़ा
इसका कोई मतलब नहीं निकलता। यदि ग्राफ में चक्र हैं, तो कोई स्थलीय सॉर्टिंग नहीं है, जिसका अर्थ है कि स्थलीय सॉर्टिंग के लिए कोई भी सही एल्गोरिदम निरस्त हो जाएगा।
जोड़ा लेखक sleske, स्रोत
@ एनब्रो मैं शर्त लगाता हूं, उनका मतलब है टोपोलॉजिकल सॉर्टिंग एल्गोरिदम का एक संस्करण जो कि जब कोई स्थलीय सॉर्टिंग मौजूद नहीं होती है (और फिर वे सभी शीर्षकों पर नहीं जाते हैं)।
जोड़ा लेखक maaartinus, स्रोत
@OlegMikheev हां, लेकिन स्टीव कह रहा है "यदि वह संख्या डीएजी में कुल संख्याओं की तुलना में कम है, तो आपके पास एक चक्र है", जो समझ में नहीं आता है।
जोड़ा लेखक nbro, स्रोत
विकिपीडिया से: कई टोपोलॉजिकल सॉर्टिंग एल्गोरिदम भी चक्रों का पता लगाएंगे, क्योंकि उनको स्थलीय क्रम के अस्तित्व में बाधाएं हैं।
जोड़ा लेखक Oleg Mikheev, स्रोत
यदि आप चक्र के साथ ग्राफ पर एक स्थलीय सॉर्टिंग करते हैं तो आप उस क्रम के साथ समाप्त हो जाएंगे जिसमें कम से कम खराब किनारों (आदेश संख्या> पड़ोसी का ऑर्डर नंबर) होगा। लेकिन जब आपको उन खराब किनारों का पता लगाना आसान हो जाता है जिसके परिणामस्वरूप चक्र के साथ ग्राफ का पता लगाना पड़ता है
जोड़ा लेखक UGP, स्रोत

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

|e| > |v| - 1

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

0
जोड़ा
काउंटर उदाहरण?
जोड़ा लेखक EralpB, स्रोत
यह अप्रत्यक्ष ग्राफ के लिए सच हो सकता है, लेकिन निश्चित रूप से निर्देशित ग्राफ के लिए नहीं।
जोड़ा लेखक Hans-Peter Störr, स्रोत
एक काउंटर उदाहरण ए-> बी, बी-> सी, ए-> सी होगा।
जोड़ा लेखक user152468, स्रोत
सभी शीर्षकों में किनारों नहीं हैं।
जोड़ा लेखक Debanjan Dhar, स्रोत

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

0
जोड़ा
सच। अजय गर्ग केवल "चक्र" को खोजने के बारे में बता रहे हैं, जो इस प्रश्न का एक हिस्सा है। आपका लिंक पूछे गए प्रश्न के अनुसार सभी चक्रों को खोजने के बारे में बात करता है, लेकिन फिर ऐसा लगता है कि यह अजय गर्ग के समान दृष्टिकोण का उपयोग करता है, लेकिन यह भी संभव है कि सभी संभावित डीएफएस-पेड़।
जोड़ा लेखक Manohar Reddy Poreddy, स्रोत
हाँ, मुझे वही लगता है, लेकिन यह पर्याप्त नहीं है, मैं अपना रास्ता पोस्ट करता हूं cs.stackexchange.com/questions/7216/find-the-simple-cycles-i‌ एन-ए-निर्देशित ग्राफ
जोड़ा लेखक jonaprieto, स्रोत

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

0
जोड़ा

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

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

0
जोड़ा

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

0
जोड़ा
सच है, अगर इनपुट के आकार के रूप में नोड्स की संख्या ली जाती है। आप किनारों या यहां तक ​​कि चक्रों, या इन उपायों के संयोजन के संदर्भ में रनटाइम जटिलता का भी वर्णन कर सकते हैं। एनागोरिदम "डोनाल्ड बी जॉनसन द्वारा निर्देशित ग्राफ के सभी प्राथमिक सर्किटों को ढूंढना" ओ ((एन + ई) (सी + 1) द्वारा दिए गए बहुपद चलने का समय है, जहां n नोड्स की संख्या है, और किनारों की संख्या है और ग्राफ के प्राथमिक सर्किट की संख्या सी। और यहां इस एल्गोरिदम का मेरा जावा कार्यान्वयन है: github.com/1123/johnson
जोड़ा लेखक user152468, स्रोत

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

0
जोड़ा
@kittyPLm यह एक खराब एल्गोरिदम नहीं है यदि आप रिकर्सिव कॉल स्टैक पर मौजूद नोड्स का ट्रैक रखते हैं।
जोड़ा लेखक Pavel, स्रोत
@ जेकग्रीन यहां देखें: i.imgur.com/tEkM5xy.png समझने के लिए काफी सरल है। मान लें कि आप 0 से शुरू करते हैं। फिर आप नोड 1 पर जाते हैं, वहां से कोई और रास्ता नहीं, पुनर्मिलन वापस चला जाता है। अब आप नोड 2 पर जाते हैं, जिसमें वर्टेक्स 1 का किनारा है, जिसे पहले से ही देखा गया था। आपकी राय में आपके पास एक चक्र होगा - और आपके पास वास्तव में कोई नहीं है
जोड़ा लेखक noisy cat, स्रोत
@ जेकग्रेन बेशक यह नहीं करता है। अपने एल्गोरिदम का उपयोग करके और 1 से शुरू करने से आप एक चक्र का पता लगाएंगे ... यह एल्गोरिदम बस खराब है ... आमतौर पर जब भी आप किसी विज़िट वर्टेक्स का सामना करते हैं तो पीछे की तरफ चलना पर्याप्त होगा।
जोड़ा लेखक noisy cat, स्रोत
1,2,3: 1,2 पर विफल 1,3; 2,3;
जोड़ा लेखक noisy cat, स्रोत
@kittyPL उस ग्राफ में एक चक्र नहीं है। विकिपीडिया से: "निर्देशित ग्राफ़ में एक निर्देशित चक्र एक ही चरम पर शुरू होने और समाप्त करने वाले अक्षरों का एक अनुक्रम है, जैसे चक्र के प्रत्येक दो लगातार शिखर के लिए, पहले के कशेरुक से बाद में एक" वी से पथ का पालन करने में सक्षम होना चाहिए जो निर्देशित चक्र के लिए वी की ओर जाता है। माफोनिया का समाधान दिए गए समस्या के लिए काम करता है
जोड़ा लेखक Jake Greene, स्रोत
@किटीपीएल क्या आप समझा सकते हैं कि वह मामला क्यों विफल रहता है? या तो 1) यह एक निर्देशित ग्राफ है और इसलिए कोई चक्र नहीं बनाया गया है या 2) डीएफएस 1 -> 2 (1,2 का उपयोग करके), 2 -> 3 (2,3 का उपयोग करके), 3 -> 1 (1 का उपयोग कर) , 3)
जोड़ा लेखक Jake Greene, स्रोत
@किटीपीएल डीएफएस दिए गए शुरुआती नोड से चक्रों का पता लगाने के लिए काम करता है। लेकिन जब डीएफएस करते हैं तो आपको बैक-एज से क्रॉस-एज को अलग करने के लिए रंगों का दौरा करना होगा। पहली बार एक कशेरुक का दौरा करने से यह भूरे हो जाता है, फिर उसके सभी किनारों का दौरा करने के बाद आप इसे काला कर देते हैं। यदि डीएफएस करते समय आप ग्रे ग्रेटेक्स हिट करते हैं तो वह कशेरुक एक पूर्वज होता है (यानी: आपके पास चक्र होता है)। यदि कशेरुका काला है तो यह सिर्फ एक क्रॉस-एज है।
जोड़ा लेखक Kyrra, स्रोत

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

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

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

0
जोड़ा
इसका वोट कम क्यों हुआ? यदि कुछ और नहीं है, तो संदर्भ विषय और संभवतः उपयोगी है।
जोड़ा लेखक David Gish, स्रोत
//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);
     }
 }


`
0
जोड़ा