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

सी ++ प्रोग्राम 4-रंग समस्या के कार्यान्वयन का प्रदर्शन करने के लिए

यह 4-रंग की समस्या के कार्यान्वयन को प्रदर्शित करने के लिए एक C++ प्रोग्राम है।

एल्गोरिदम

Begin
   Develop function issafe() to check if the current color assignment
   is safe for vertex v i.e. checks whether the edge exists or not.
   If it exists,
      then next check whether the color to be filled in the new vertex is already used by its adjacent vertices.
End
Begin
   Function graphColoringtil(bool graph[V][V], int m, int col[], int v)
   solve 4 coloring problem:
   Here,
   g[V][V] = It is a 2D array where V is the number of vertices in graph
   m = maximum number of colors that can be used.
   col[] = an color array that should have numbers from 1 to m.
   if v == V
      return true
   For c = 1 to m
      if (isSafe(v, g, col, c))
         col[v] = c
         if (graphColoringtil (g, k, col, v+1) == true)
            return true
         col[v] = 0
   return false
End

Begin
   function graphColor():
      It mainly uses graphColoringUtil() to solve the problem.
         It returns false if the m colors cannot be assigned,
            otherwise return true.
End

उदाहरण

#include <iostream>
#include <cstdio>
#define V 5
using namespace std;
bool isSafe (int v, bool graph[V][V], int col[], int C) {
   for (int i = 0; i < V; i++)
   if (graph[v][i] && C == col[i])
   return false;
   return true;
}
bool graphColoringtil(bool g[V][V], int k, int col[], int v) {
   if (v == V) //If all vertices are assigned a color then
   return true;
   for (int c = 1; c <= k; c++) { //Consider this vertex v and try different colors
      if (isSafe(v, g, col, c)) { //Check if assignment of color c to v is fine
         col[v] = c;
         if (graphColoringtil (g, k, col, v+1) == true) //recur to assign colors to rest of the vertices
            return true;
         col[v] = 0; //If assigning color c doesn't lead to a solution then remove it
      }
   }
   return false;
}
void solution(int color[]) {
   cout<<"The assigned colors are: \n";
   for (int i = 0; i < V; i++)
      cout<<color[i];
   cout<<"\n";
}
bool graphColor(bool graph[V][V], int k) {
   int *color = new int[V];
   //initialize all colors value as 0
   for (int i = 0; i < V; i++)
   color[i] = 0;
   if (graphColoringtil(graph, k, color, 0) == false) {
      cout<<"Solution does not exist";
      return false;
   }
   solution(color);
   return true;
}
int main() {
   bool g[V][V] = {
      {0, 0, 1, 0,1},
      {1, 1, 1, 0,0},
      {1, 1, 0, 0,1},
      {0, 1, 1, 0,0}
   };
   int k= 4;
   graphColor(g, k);
   return 0;
}

आउटपुट

The assigned colors are:
1 2 3 1 1

  1. टीम के सदस्यों के सूचकांकों के अनुक्रम को खोजने के लिए C++ प्रोग्राम

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

  1. C++ प्रोग्राम ग्राफ में सुपर वर्टिस का पता लगाने के लिए

    मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्ष हैं। कोने 1 से n तक गिने जाते हैं, और वे सरणी किनारों में दिए गए किनारों से जुड़े होते हैं। प्रत्येक शीर्ष का 1 से n तक की संख्या के भीतर x मान होता है जो कि सरणी मान में दिया जाता है। अब, हमें ग्राफ से अति शीर्षों का पता लगाना है। एक शीर्ष i को सु

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

    दिए गए डेटा को सॉर्ट करने के लिए शेकर सॉर्ट का उपयोग किया जाता है। बबल सॉर्ट के विपरीत, शेकर सॉर्ट, दोनों दिशाओं में सरणी को ऑर्डर करता है। इस एल्गोरिथम की सबसे खराब जटिलता O(n^2) है। एल्गोरिदम Begin    ShakerSort() function has ‘arr’ the array of data and ‘n’ the n