कैसे पता लगाया जाए कि एक निर्देशित ग्राफ चक्रीय है या नहीं?

Question

हम कैसे पता लगा सकते हैं कि एक निर्देशित ग्राफ चक्रीय है या नहीं? मैंने पहली बार चौड़ाई खोज का उपयोग किया, लेकिन मुझे यकीन नहीं है। कोई विचार?

Answer 1

आमतौर पर गहराई से पहले खोज का उपयोग किया जाता है। मुझे नहीं पता कि बीएफएस आसानी से लागू होता है या नहीं।

DFS में, एक स्पैनिंग पेड़ का दौरा करने के लिए बनाया गया है। यदि पेड़ में नोड के पूर्वजों का दौरा किया जाता है (यानी बैक-एज बनाया जाता है), तो हम एक चक्र का पता लगाते हैं।

अधिक विस्तृत स्पष्टीकरण के लिए http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf देखें।

Answer 2

एक और आसान समाधान एक मार्क-एंड-स्वीप दृष्टिकोण होगा। असल में, पेड़ में प्रत्येक नोड के लिए आप इसे "विज़िट" के रूप में चिह्नित करते हैं और फिर उसके बच्चों पर जाते हैं। यदि आप कभी भी "visted" ध्वज सेट के साथ नोड देखते हैं, तो आप जानते हैं कि एक चक्र है।

यदि "विज़िट" बिट शामिल करने के लिए ग्राफ़ को संशोधित करना संभव नहीं है, तो इसके बजाय नोड पॉइंटर्स का एक सेट उपयोग किया जा सकता है। किसी नोड को विज़िट करने के लिए फ़्लैग करने के लिए, आप सेट में पॉइंटर डालते हैं। यदि सूचक पहले से ही सेट में है, तो एक चक्र है।

Answer 3

क्या तुम सच में की जरूरत है, मुझे विश्वास है, एक की तरह एक सांस्थितिकीय छंटाई एल्गोरिथ्म यहाँ वर्णित है: निर्देशित ग्राफ एक चक्र है

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

तो एल्गोरिथ्म असफल हो जायेगी।

टिप्पणियां/उत्तर जिन्हें मैंने अब तक देखा है, इस तथ्य को याद नहीं कर रहे हैं कि में ग्राफ़ निर्देशित किया गया है, वहां नोड एक्स से नोड वाई तक पहुंचने के एक से अधिक तरीके हो सकते हैं, बिना किसी निर्देशित (निर्देशित) ग्राफ में चक्र।

Answer 4

दृष्टिकोण: 1
एक चक्र का पता लगाने के लिए स्तर के असाइनमेंट के बारे में कैसे। उदाहरण: नीचे दिए गए ग्राफ पर विचार करें। ए -> (बी, सी) बी-> डी डी -> (ई, एफ) ई, एफ -> (जी) ई-> डी जैसा कि आप एक डीएफएस निष्पादित करते हैं, जिस नोड पर आप नोड के स्तर को असाइन करते हैं (रूट ए = 0)। नोड = पैरेंट + 1 का स्तर संख्या। तो ए = 0, बी = 1, डी = 2, एफ = 3, जी = 4 फिर, रिकर्सन डी तक पहुंचता है, इसलिए ई = 3। जी के लिए मार्क स्तर न करें (जी पहले से ही एक स्तर का असाइन किया गया है जो ई से ग्रेटर है) अब ई के पास डी के लिए भी बढ़त है। इसलिए स्तरीयरण कहता है कि डी को 4 का स्तर नहीं होना चाहिए। लेकिन डी में पहले से ही "निचला स्तर" असाइन किया गया है 2. यह करने के लिए इस प्रकार किसी भी समय आप जबकि डीएफएस पहले से ही एक निचले स्तर संख्या यह करने के लिए सेट है कि कर एक नोड के लिए एक स्तर संख्या असाइन करने का प्रयास .., तुम्हें पता है निर्देशित ग्राफ एक चक्र है

approach2:
3 रंगों का प्रयोग करें। सफेद, भूरा, काला। रंग केवल सफेद नोड्स, सफेद नोड्स ग्रे के रूप में जब आप डीएफएस नीचे जाते हैं, रंग ग्रे ग्रे नोड्स रिक्त होने पर काला होते हैं (सभी बच्चों को संसाधित किया जाता है)। अगर सभी बच्चों को अभी तक संसाधित नहीं किया गया है और आप एक ग्रे नोड को एक चक्र से मारते हैं। उदाहरण: सभी सफेद सीधे ऊपर ग्राफ में शुरू करने के लिए। रंग ए, बी, डी, एफ, जी रंगीन सफेद भूरे रंग के हैं। जी पत्ती है इसलिए सभी बच्चों ने इसे भूरे रंग से काले रंग में संसाधित किया। पुनरावृत्ति एफ को प्रकट होती है (सभी बच्चों को संसाधित) इसे काला रंग दें। अब आप डी तक पहुंचते हैं, डी में अनप्रचारित बच्चे हैं, इसलिए रंग ई ग्रे, जी पहले से ही रंगीन काला है, इसलिए आगे नहीं जाएं। ई में डी के किनारे भी है, इसलिए डी (डी अभी भी ग्रे) को प्रोसेस करते समय, आपको डी (ग्रे ग्रे नोड) पर एक किनारे मिलते हैं, एक चक्र का पता चला है।

Answer 5

दिए गए ग्राफ पर टॉपोलॉजिकल सॉर्ट के लिए परीक्षण आपको समाधान के लिए ले जाएगा। यदि टॉपसॉर्ट के लिए एल्गोरिदम, यानी किनारों को हमेशा एक तरह से निर्देशित किया जाना चाहिए, तो इसका मतलब है कि ग्राफ में चक्र होते हैं।यदि कोई पथ चक्रीय है खोज करने के लिए

Answer 6

उपयोग डीएफएस

class Node<T> { T value; List<Node<T>> adjacent; } 

class Graph<T>{ 

    List<Node<T>> nodes; 

    public boolean isCyclicRec() 
    { 

     for (Node<T> node : nodes) 
     { 
      Set<Node<T>> initPath = new HashSet<>(); 
      if (isCyclicRec(node, initPath)) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 

    private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path) 
    { 
     if (path.contains(currNode)) 
     { 
     return true; 
     } 
     else 
     { 
     path.add(currNode); 
     for (Node<T> node : currNode.adjacent) 
     { 
      if (isCyclicRec(node, path)) 
      { 
       return true; 
      } 
      else 
      { 
       path.remove(node); 
      } 
     } 
     } 
     return false; 
    } 

की