Graph Coloring Problem using Backtracking in C Program

#include <stdio.h>
int v;

int issafe(int mat[v][v], int color[v], int c, int v1){
    for(int i=0; i<v; i++){
        if(mat[v1][i] && c==color[i]) 
            return 0;
    }
    return 1;
}

int graphcoloring(int mat[v][v],int m,int v1,int color[v]){
    if(v1==v)
        return 1;

    for(int c=1;c<=m;c++){
        if(issafe(mat,color,c,v1)==1){
            color[v1]=c;

            if(graphcoloring(mat,m,v1+1,color)==1) return 1;

            color[v1]=0;
        }
    }

    return 0;
}

void printsol(int color[])
{
    printf("Solution: \n");
    printf("Vertex  Color \n");
    for (int i = 0; i < v; i++)
        printf("%d\t %d\n", i+1, color[i]);
}

void graphcolor(int mat[v][v], int m){
    int color[v];
    for(int i=0; i<v; i++)
        color[i]=0;

    if(graphcoloring(mat,m,0,color)==0){
        printf("Solution not possible!");
        return;
    }
    printsol(color);
    
}

int main(){
    printf("Enter number of vertex: ");
    scanf("%d",&v);
    int m;
    printf("Enter number of colors: ");
    scanf("%d",&m);
    int mat[v][v];
    printf("Enter adjacency matrix: \n");
    for(int i=0; i<v; i++){
        for(int j=0; j<v; j++){
            scanf("%d",&mat[i][j]);
        }
    }
    graphcolor(mat,m);
    return 0;
}

Output -

Enter number of vertex: 7
Enter number of colors: 4
Enter adjacency matrix: 
0 1 1 0 1 1 0
1 0 0 1 0 1 1 
1 0 0 1 1 1 0 
0 1 1 0 0 1 1 
1 0 1 0 0 0 1 
1 1 1 1 0 0 0 
0 1 0 1 1 0 0
Solution: 
Vertex  Color
1        1
2        2
3        2
4        1
5        3
6        3
7        4

More like this -

• Fractional Knapsack Problem

• Job Sequencing with Deadline

• Naive String Matching Algorithm

• KMP String Matching Algorithm

• Prims Algorithm

• Kruskal's Algorithm

• 15 Puzzle Problem