एक स्पैनिंग पेड़ ढूंढना जो नोड्स की गहराई के योग को कम करता है

Question

मेरे पास अनियंत्रित किनारों वाला एक अप्रत्यक्ष कनेक्टेड ग्राफ़ है। मैं एक स्पैनिंग पेड़ कैसे बना सकता हूं (समाधान अद्वितीय नहीं हो सकता है) जैसे कि सभी नोड्स की गहराई का योग कम हो गया है? यह स्पष्ट रूप से न्यूनतम स्पैनिंग पेड़ नहीं ढूंढ रहा है, क्योंकि किनारों के "वजन" वास्तव में बच्चे की गहराई के आधार पर भिन्न होते हैं।

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

Answer 1

क्या यह एक वैध एल्गोरिदम है?

हां, एल्गोरिदम सही है।

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

एल्गोरिदम द्वारा निर्मित पेड़ प्रत्येक नोड को R से सबसे कम पथों में से एक के साथ जोड़ता है, इसलिए गहराई का योग दूरी की राशि है, जिसे हमने उपरोक्त देखा है, वह कम बाध्य है।

एक छोटे अनुकूलन के रूप में, यदि नोड्स की संख्या कम से कम 3 है, तो डिग्री 1 के साथ कोई नोड पेड़ की जड़ के रूप में नहीं माना जाना चाहिए। (डिग्री 1 के साथ एक नोड R पर रूट किए गए पेड़ के लिए, उसी ग्राफ पर विचार करें, जिसे R पड़ोसी पर रूट किए गए पेड़ के रूप में देखा जाता है। R की गहराई 1 से बढ़ जाती है, अन्य सभी नोड्स की गहराई 1 से घट जाती है, इसलिए योग number_of_nodes - 2 द्वारा गहराई में कमी आती है।)