CODEWITHSUNDEEP
c++algorithmbacktracking
user46562
user46562

Reputation: 31

Graph Colouring in using adjacency matrix

I am trying to solve the coloring problem with backtracking. I am unable to get proper output, but my logic is correct. I should get 1 2 3 2, but I am getting 1 2 2 2. What is going wrong?

#include <iostream>

using namespace std;

#define V 4


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


bool graphColoring(bool graph[V][V], int m, int v, int color[V])
{
    if (v == V)
        return true;

    for (int i = 1; i <= m; i++) {
        if (isitsafetocolourVwiththisC(graph, v, i, color))
        {
            color[v] = i;
            if (graphColoring(graph, m, v+1, color))
                return true;
            color[v] = 0;
        }
    }
    return false;
}


void printcolours(int color[V])
{
    for (int i = 0; i < V; i++)
        cout << color[i] << " ";
}


int main()
{

    bool graph[V][V] = {{0, 1, 1, 1},
                        {1, 0, 1, 0},
                        {1, 1, 0, 1},
                        {1, 0, 1, 0}};
    int m = 3; // Number of colors
    int color[V];
    memset(color, 0, sizeof color);
    bool flag = graphColoring(graph, m, 0, color);
    if (flag)
        printcolours(color);
    else 
        cout << "Solution doesn't exist.";
    return 0;
}

Upvotes: 2

Views: 1255

Answers (1)

Arya McCarthy
Arya McCarthy

Reputation: 8829

If your logic is correct, your output will be correct. ;)

I ran this myself to confirm, after I moved return true out of the for-loop. It works correctly now.

bool isitsafetocolourVwiththisC(bool graph[V][V], int v, int c, int color[V])
{
    for(int i=0;i<V;i++)
    {
        if(graph[v][i] &&  (c == color[i]))
            return false;
        // Not returning here anymore!
    }
    return true;
}

The reason is that in the other place, you never process any other elements of the list. You must return true or false after the first element.

I don't know which compiler you're using, but clang complains with your original code—let the compiler help you.

myfile.cpp:15:1: warning: control may reach end of non-void function
      [-Wreturn-type]
}

Upvotes: 2

Related Questions