ग्राफ एल्गोरिदम खोज रहा है कि ग्राफ कनेक्ट होने पर, द्विपक्षीय, चक्र है और एक पेड़ है

Question

जब मैं ग्राफ के साथ काम करने की कोशिश कर रहा था और इसके लिए कुछ कोड लिख रहा था, लेकिन कोई भाग्य नहीं:/!!

मेरे द्वारा बनाए गए कुछ है कि ग्राफ के डेटा लेने के लिए और जाँच करेगा अगर यह होता है चाहता था: 1- जुड़े 2- द्विपक्षीय 3 चक्र 4- एक पेड़

तो

मैं सोच रहा था है उदाहरण के लिए यदि यह एक .txt फ़ाइल से ग्राफ़ डेटा पढ़ने के लिए लिखा जा सकता है जो उपर्युक्त परीक्षण करेगा ??

सरल किनारे-सूची प्रारूप का उपयोग कर इसके लिए सही दृष्टिकोण है?

आपकी सहायता की सराहना की जाती है यदि आप मुझे इस कार्य को कैसे करना है या कोड के लिए किक शुरू करने के बारे में पढ़ने के लिए एक लिंक दे सकते हैं !!

धन्यवाद: डी

Answer 1

जांच अगर यह होता है:

1. जुड़े

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

प्रत्येक नोड c के लिए

• मार्क सभी नोड्स, अगर इस नोड विज़िट नहीं किए गए
  • नोड्स का एक नया खाली सेट बनाने है, वर्तमान घटक
  • ट्रेवर्सल
  • के लिए इस नोड enqueue जबकि वहाँ है किसी भी नोड t कतारबद्ध
    • इस मंजूरी को दूर कतार से ई
    • निशान हर विज़िट नहीं किए गए पड़ोसी के रूप में खुला और
    • निशान इस नोड ट्रेवर्सल के लिए यह enqueue के रूप में चल
    • वर्तमान घटक
  • वर्तमान घटक बंद करने के लिए इस नोड जोड़ सकते हैं और इसे जोड़ने घटकों

अगर वहाँ केवल एक घटक है के सेट करने के लिए, ग्राफ जुड़ा हुआ है।

यदि कोई कतार का उपयोग किया जाता है, तो एल्गोरिदम एक चौड़ाई-पहली खोज है। यदि एक स्टैक का उपयोग किया जाता है, तो एल्गोरिदम एक गहराई-पहली खोज है। पुश और पॉप-किसी भी ऑपरेशन के साथ कोई अन्य संग्रह करेगा। विशेष रुचि में कॉल-स्टैक है: "ट्रैवर्सल" के लिए "ट्रैवर्सल के लिए एनक्यू"

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

1. द्विपक्षीय

एक ग्राफ iff यह bicolorable है द्विपक्षीय है। एक bicoloring असाइन करने का प्रयास करें, और यदि आप असफल हो, तो ग्राफ द्विपक्षीय नहीं है। इसे पिछले एल्गोरिदम में शामिल किया जा सकता है: जब भी आप एक नोड को खुले के रूप में चिह्नित करते हैं, तो उसके पड़ोसी t को दिए गए रंग के विपरीत, इसके लिए एक रंग असाइन करें। जब t का पड़ोसी पहले से ही खुला है, तो उसका रंग जांचें। तो उसका रंग t की तरह ही है, वहाँ कोई bicoloring है।

1. चक्र

है यह एक आसान है: आप किसी भी नोड कि पहले से ही खुला है, वहाँ एक चक्र है दिखाई देती है तो। ध्यान दें कि प्रत्येक ग्राफ जिसमें कोई चक्र नहीं है, द्विपक्षीय है।

निर्देशित ग्राफ में, यह एक अप्रत्यक्ष चक्र की उपस्थिति का पता लगाएगा। निर्देशित चक्रों की उपस्थिति का पता लगाने के लिए, निम्न (सांस्थितिक तरह) कलन विधि का उपयोग करें: जबकि वहाँ शून्य

• की indegree साथ एक नोड है
  • (चक्र का पता लगाने के लिए अप्रासंगिक) संस्थानिक प्रकार के नोड जोड़ते क्या अब भी कोई ग्राफ
    • में किसी भी नोड है
    • ग्राफ
  • से नोड को दूर ग्राफ एक निर्देशित cycl शामिल ई। कोई संस्थानिक तरह कि ग्राफ
• बाकी
  • ग्राफ एक निर्देशित चक्र शामिल नहीं है (अचक्रीय है) पर मौजूद है। उत्पन्न स्थलीय प्रकार मान्य है।

1. पेड़

एक अनिर्दिष्ट ग्राफ एक पेड़ iff यह जुड़ा हुआ है और कोई चक्र होता है।

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