एक अप्रत्यक्ष ग्राफ

Question

में कनेक्ट किए गए घटकों की संख्या मैं कुछ ग्राफ एल्गोरिदम पर जा रहा हूं (यह होमवर्क नहीं है; मैं सिर्फ एल्गोरिदम और डेटा-स्ट्रक्चर पर ब्रश कर रहा हूं) और मेरे पास एक प्रश्न है। मान लें मैं निम्नलिखित अनिर्दिष्ट ग्राफ है:

var graph = { 
    9: [19, 26], 
    13: [19, 5], 
    17: [], 
    26: [11, 18], 
    18: [9], 
    19: [], 
    23: [24], 
    24: [], 
    11: [], 
    18: [] 
}; 

ग्राफ मूल रूप से इस तरह दिखता है:

कितने कनेक्टेड घटकों इस ग्राफ में कर रहे हैं? ग्राफ को देखने से, ऐसा लगता है कि 3 घटक हैं। लेकिन अगर मैं वास्तव में एल्गोरिदम लागू करता हूं (प्रत्येक चरम पर पुनरावृत्ति करता हूं, और उस कशेरुक का उपयोग करते हुए एक बीएफएस को के रूप में उपयोग करते हैं, तो कि वर्टेक्स अनदेखा है। इसके अलावा, बीएफएस किसी भी चरम पर चिह्नित होगा, जैसा कि खोजा गया है)।

यदि मैं 9 से शुरू करता हूं, तो मैं निम्नलिखित नोड्स को खोजता हूं: [19, 26, 11, 18]। हालांकि, 13 खोज नहीं है क्योंकि यह 19 की आसन्नता सूची में नहीं है। हालांकि, 1913 की आसन्नता सूची में है। यही कारण है कि मैं एक अतिरिक्त घटक के साथ समाप्त होता है।

क्या यह सही है? क्या वास्तव में 4 अलग-अलग घटक हैं और यदि हां, तो क्या कनेक्टेड घटकों की मेरी समझ गलत है?

Answer 1

समस्या

अनिर्दिष्ट ग्राफ की निकटता सूची अभ्यावेदन के लिए, आप या तो

(1) सममित समीपता सूचियों का उपयोग, अर्थात् जब एक नई धार ab में डालने, badjlist[a]और में जोड़ने के लिए है कि है इसके विपरीत

या

(2) पार सब कोने 'निकटता सूचियों everytim ई आप एक बढ़त के अस्तित्व के लिए देख रहे हैं।

चूंकि (2) बहुत अक्षम है, आप आमतौर पर (1) के साथ जाते हैं। यह सामान्य रूप से उपयोग की जाने वाली एडी सूचियों के लिए भी सम्मेलन है। अगर मुझे आपकी एडी सूची के साथ प्रस्तुत किया गया था, तो मुझे लगता है कि ग्राफ निर्देशित किया गया था।

Answer 2

आप अपनी आसन्न सूची प्रतिनिधित्व बदल सकते हैं, आपका प्रतिनिधित्व 'निर्देशित' है लेकिन आपकी तस्वीर अप्रत्यक्ष है। किनारे के लिए (ए, बी) ग्राफ {ए: [बी], बी: [ए]}