CPP

graph colouring backtracking

class GrpahColouring {
  public:
    int V = 4;
 
  bool isSafeToColor(int v, vector < vector < int >> & graphMatrix, vector < int > color, int c) {
    for (int i = 0; i < V; i++)
      if (graphMatrix[v][i] == 1 && c == color[i])
        return false;
    return true;
  }
 
  bool graphColorUtil(vector < vector < int >> & graphMatrix, int m, vector < int > color, int v) {
    if (v == V)
      return true;
 
    for (int i = 1; i <= m; i++) {
      if (isSafeToColor(v, graphMatrix, color, i)) {
        color[v] = i;
        if (graphColorUtil(graphMatrix, m, color, v + 1))
          return true;
        color[v] = 0;
      }
    }
    return false;
  }
 
  void printColoringSolution(int color[]) {
    cout << ("Color schema for vertices are: ") << endl;
    for (int i = 0; i < V; i++)
      cout << (color[i]) << endl;
  }
  bool graphColoring(vector < vector < int >> & graphMatrix, int m) {
    vector < int > color(V, 0);
 
    if (!graphColorUtil(graphMatrix, m, color, 0)) {
      cout << "Color schema not possible" << endl;
      return false;
    }
 
    printColoringSolution(color);
    return true;
  }