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

C++ प्रोग्राम: 4-Color Problem का कार्यान्वयन


यह C++ प्रोग्राम प्रसिद्ध 4-Color Problem (Four Color Theorem) को दर्शाता है। यह समस्या बताती है कि किसी भी प्लैनर मैप को केवल 4 रंगों से इस तरह कलर किया जा सकता है कि कोई भी दो आसन्न क्षेत्र एक ही रंग के न हों। प्रोग्राम बैकट्रैकिंग एल्गोरिदम का उपयोग करके ग्राफ के वर्टेक्स को कलर करता है।

एल्गोरिदम

शुरुआत
  1. फंक्शन isSafe(): जांचें कि वर्टेक्स v के लिए वर्तमान कलर असाइनमेंट सुरक्षित है या नहीं।
     - यदि एज मौजूद है, तो जांचें कि नए वर्टेक्स में भरा जाने वाला कलर
       उसके आसन्न वर्टेक्स द्वारा पहले से उपयोग तो नहीं किया गया।
  2. फंक्शन graphColoringUtil(): 4-कलरिंग समस्या हल करें:
     - g[V][V] = 2D ऐरे जहां V वर्टेक्स की संख्या है
     - m = उपयोग किए जा सकने वाले अधिकतम रंग
     - col[] = कलर ऐरे जिसमें 1 से m तक के नंबर हों
     - यदि v == V तो true लौटाएं (सभी वर्टेक्स कलर हो गए)
     - c = 1 से m तक:
         यदि isSafe(v, g, col, c) है:
             col[v] = c
             यदि graphColoringUtil(g, m, col, v+1) true है तो true लौटाएं
             col[v] = 0 (बैकट्रैक)
     - false लौटाएं
  3. फंक्शन graphColor(): मुख्य रूप से graphColoringUtil() का उपयोग करके समस्या हल करता है।
समाप्ति

उदाहरण कोड

#include <iostream>
#include <cstdio>
#define V 5
using namespace std;

bool isSafe(int v, bool graph[V][V], int color[], int c) {
    for (int i = 0; i < V; i++)
        if (graph[v][i] && c == color[i])
            return false;
    return true;
}

bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {
    if (v == V) return true; // सभी वर्टेक्स कलर हो गए
    
    for (int c = 1; c <= m; c++) {
        if (isSafe(v, graph, color, c)) {
            color[v] = c;
            if (graphColoringUtil(graph, m, color, v + 1))
                return true;
            color[v] = 0; // बैकट्रैक
        }
    }
    return false;
}

void printSolution(int color[]) {
    cout << "The assigned colors are: \n";
    for (int i = 0; i < V; i++)
        cout << color[i] << " ";
    cout << "\n";
}

bool graphColoring(bool graph[V][V], int m) {
    int *color = new int[V];
    for (int i = 0; i < V; i++) color[i] = 0;
    
    if (!graphColoringUtil(graph, m, color, 0)) {
        cout << "Solution does not exist";
        return false;
    }
    printSolution(color);
    return true;
}

int main() {
    bool graph[V][V] = {
        {0, 0, 1, 0, 1},
        {1, 1, 1, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0}  // 5वीं पंक्ति जोड़ी गई
    };
    int m = 4;
    graphColoring(graph, m);
    return 0;
}

आउटपुट

The assigned colors are: 1 2 3 1 1

महत्वपूर्ण नोट: मूल कोड में ग्राफ मैट्रिक्स में केवल 4 पंक्तियाँ थीं जबकि V=5 था। मैंने 5वीं पंक्ति जोड़ दी है। Four Color Theorem के अनुसार, कोई भी प्लैनर ग्राफ अधिकतम 4 रंगों से कलर किया जा सकता है। यह प्रोग्राम बैकट्रैकिंग का उपयोग करके एक वैध कलरिंग खोजता है।

  1. - C++ प्रोग्राम: टीम सदस्यों के सूचकांकों का अनुक्रम ढूंढें

    मान लीजिए हमारे पास n तत्वों वाला एक सरणी A और एक संख्या k है। एक कक्षा में n छात्र हैं। i-वें छात्र की रेटिंग A[i] है। हमें k छात्रों के साथ एक टीम बनानी है जैसे कि सभी टीम सदस्यों की रेटिंग अलग-अलग हो। यदि संभव नहीं है तो Impossible वापस करें, अन्यथा सूचकांकों का अनुक्रम वापस करें। उदाहरण के लिए,

  1. ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स वाला एक ग्राफ दिया गया है। वर्टेक्स 1 से n तक संख्याबद्ध हैं और edges सरणी में दी गई एज्स से जुड़े हैं। प्रत्येक वर्टेक्स का एक x मान है जो 1 से n के बीच होता है, यह values सरणी में दिया गया है। हमें ग्राफ में सुपर वर्टेक्स खोजने हैं। एक वर्टेक्स i को सुपर वर्टेक्स कहा जाता है

  1. - शेकर सॉर्ट करने के लिए C++ प्रोग्राम

    शेकर सॉर्ट का उपयोग दिए गए डेटा को सॉर्ट करने के लिए किया जाता है। बबल सॉर्ट के विपरीत, शेकर सॉर्ट सरणी को दोनों दिशाओं में ऑर्डर करता है। इस एल्गोरिदम की सबसे खराब जटिलता O(n^2) है। एल्गोरिदम शुरुआत    ShakerSort() फ़ंक्शन में arr डेटा की सरणी और n मानों की संख्या, आर्गुमेंट सूची में होती