Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में पूर्ण ग्राफ से अधिकतम संभव एज-डिसजॉइंट स्पैनिंग ट्री


मान लीजिए हमारे पास एक पूर्ण ग्राफ है; हमें एज-डिसजॉइंट स्पैनिंग ट्री की संख्या गिननी है। एज-डिसजॉइंट स्पैनिंग ट्री वे स्पैनिंग ट्री हैं, जहां सेट में कोई दो ट्री एक एज साझा नहीं करते। मान लीजिए N (शीर्षों की संख्या) 4 है, तो आउटपुट 2 होगा। 4 शीर्षों का उपयोग करके पूर्ण ग्राफ नीचे जैसा है -

C++ में पूर्ण ग्राफ से अधिकतम संभव एज-डिसजॉइंट स्पैनिंग ट्री

दो एज-डिसजॉइंट स्पैनिंग ट्री नीचे जैसे हैं -

C++ में पूर्ण ग्राफ से अधिकतम संभव एज-डिसजॉइंट स्पैनिंग ट्री

N शीर्षों वाले पूर्ण ग्राफ से अधिकतम एज-डिसजॉइंट स्पैनिंग ट्री की संख्या $[\frac{n}{2}]$ होगी।

उदाहरण

#include <iostream> #include <cmath> using namespace std; int maxEdgeDisjointSpanningTree(int n){    return floor(n/2); } int main() {    int n = 4;    cout << "Maximum Edge Disjoint Spanning Tree: " <<    maxEdgeDisjointSpanningTree(n); }

आउटपुट

Maximum Edge Disjoint Spanning Tree: 2

  1. C++ में अधिकतम बाइनरी ट्री निर्माण C++ में अधिकतम बाइनरी ट्री निर्माण

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसके सभी तत्व अद्वितीय हैं। एक अधिकतम बाइनरी ट्री निम्न नियमों से बनता है: रूट सरणी का अधिकतम तत्व होता है। बायाँ सबट्री अधिकतम तत्व के बाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है। दायाँ सबट्री अधिकतम तत्व के दाएँ भाग से बने सबसरणी का अधिकतम ट्री होता है।

  1. C++ में पूर्ण बाइनरी ट्री के नोड्स गिनें C++ में पूर्ण बाइनरी ट्री के नोड्स गिनें

    मान लीजिए हमारे पास एक पूर्ण बाइनरी ट्री है, हमें नोड्स की संख्या गिननी है। तो यदि ट्री इस तरह है −तो आउटपुट 6 होगा।इसे हल करने के लिए, हम इन चरणों का पालन करेंगेयह रिकर्सिव दृष्टिकोण का उपयोग करेगा। यह मेथड, countNodes() रूट को आर्गुमेंट के रूप में ले रहा है।hr := 0 और hl := 0दो नोड्स l और r

  1. C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम ढूंढेगा।बाइनरी ट्री का स्पाइरल सम  बाइनरी ट्री के स्पाइरल ट्रैवर्सल में मिलने वाले नोड्स का योग है।ट्री के स्पाइरल ट्रैवर्सल में, नोड्स को रूट से लीफ नोड तक ट्रैवर्स कि