7
मैं अपना होमवर्क पर निम्नलिखित समस्या है:पता लगाएं कि न्यूनतम स्पैनिंग पेड़ में रैखिक समय में किनारे हैं या नहीं?
एक हे दें (n + m) लगाने के लिए एल्गोरिथ्म है कि एक बढ़त ई एक ग्राफ
की MST का एक हिस्सा हो सकता है कि क्या (हमें इस असाइनमेंट पर दूसरों से मदद प्राप्त करने की इजाजत है, इसलिए यह धोखाधड़ी नहीं है।)
मुझे लगता है कि मैं एक बीएफएस कर सकता हूं और यह पता लगा सकता हूं कि यह किनारा दो परतों के बीच एक किनारा है और यदि ऐसा है तो यह किनारा था उन परतों में सबसे छोटा। लेकिन मैं यह कह सकता हूं कि यह किनारा बीएफएस पेड़ का पेड़ किनारा नहीं है?
यदि यह होमवर्क है, तो इसे चिह्नित करें। –