ओ (वी * ई) के बजाय बीएफएस ओ (वी + ई) की जटिलता क्यों है?

Question

कुछ स्यूडोकोड यहाँ

v1 से शुरू (मेरी शैली उपेक्षा) (कतारबद्ध):

function BFS(queue Q) 
    v2 = dequeue Q 
    enqueue all unvisited connected nodes of v2 into Q 
    BFS(Q) 
end // maybe minor problems here 

चूंकि ग्राफ में वी कोने हैं, और ये वी कोने ई किनारों से जुड़े हैं, और विजिटिंग हो रही जुड़े नोड्स (जुड़े हुए किनारों के दौरे के बराबर) आंतरिक पाश में है (बाहरी पाश खुद ही रिकर्सन है), ऐसा लगता है कि जटिलता ओ (वी + ई) की बजाय ओ (वी * ई) होना चाहिए। क्या कोई इसे मेरे लिए समझा सकता है?

Answer 1

ई प्रत्येक चरम के निकट किनारों की संख्या नहीं है - इसकी वास्तव में ग्राफ में किनारों की कुल संख्या है। इसे इस तरह परिभाषित करना उपयोगी है क्योंकि आपके पास प्रत्येक कशेरुक पर समान संख्या में किनारों की आवश्यकता नहीं है।

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