साझा सीमाओं के साथ न्यूनतम कनेक्टिंग क्षेत्रों के लिए ग्राफी थ्योरी एल्गोरिदम

Question

मेरे पास प्रत्येक "पेन पेन" का भारित ग्राफ है जिसमें प्रत्येक पेन में कम से कम 3 किनारों/अंक और कम से कम दो पेन होते हैं। मुझे सभी पेन जोड़ने के लिए निकालने के लिए न्यूनतम भारित किनारों को समझना होगा (आप बाहरी किनारों को हटाकर उन्हें अन्य पेन से कनेक्ट नहीं कर सकते हैं)।

क्या कोई एल्गोरिदम या एक प्रक्रिया की सिफारिश कर सकता है जिसके साथ मैं न्यूनतम भारित दीवारों को हटाने के लिए संपर्क कर सकता हूं। मैं प्राइम के एल्गोरिदम के बारे में सोच रहा था लेकिन मुझे पूरी तरह से यकीन नहीं है कि मैं इसे कैसे लागू कर सकता हूं।

यह मैं नहीं है इस सवाल का जवाब अभी तक कैसे पहुंचेंगे करने के लिए के रूप में कुछ दिशा चाहते http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

पर समस्या एस 4 है यह

Answer 1

आप सही दिशा में हैं।

मॉडल एक अनिर्दिष्ट ग्राफ के रूप में आपकी समस्या G=(V,E) जहां V = { all pens }, E = { (u,v) | there is a wall between u and v }w((u,v)) = cost of wall between u and v

आदेश "सब कलम कनेक्ट" करने के साथ - आप वास्तव में एक subgraph के लिए देख रहे हैं: G'=(V,E') ऐसी है कि उप ग्राफ G' जोड़ा जाएगा [ प्रत्येक दो नोड्स के बीच एक रास्ता है], और ई में दीवारों की लागत न्यूनतम है।

इसे कम से कम लागत पर प्राप्त करने के लिए - आप Minimum Spanning Tree की तलाश में हैं। [यह देखना आसान है कि आपको वास्तव में एक पेड़ की आवश्यकता है - क्योंकि पेड़ बनाने के बाद कोई अतिरिक्त किनारा अनावश्यक है और ग्राफ की कनेक्टिविटी को नुकसान पहुंचाए बिना हटाया जा सकता है - या समस्या अवधि में - आप एक दीवार को पुनर्स्थापित कर सकते हैं और पेन जुड़ा]

दो संभव एल्गोरिदम कि आप MST मिल जाएगा रहे हैं Prim और Kruskal