Graph Coloring algorithm using backtracking in c
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:#include<stdio.h> int G[10][10],m,edges,color_tab[10],v1,v2,i,j,n,a,b; void Gen_Col_Value(int,int); void Gr_coloring(int,int); int main() { printf("\nEnter the number of nodes & edges\n"); scanf("%d%d",&n,&edges); m=n-1; printf("\nEnter the edges of the graph\n\n"); for (i=1;i<=edges; i++) { printf("Enter value of x,y\n"); scanf("%d%d",&v1,&v2); G[v1][v2] = G[v2][v1] = 1; printf("\n"); } Gr_coloring(1,n); printf("\n The Vertices To be Coloured As...\n"); for(i=1;i<=n;i++) printf("\n V%d:=%d",i,color_tab[i]); return 0; } void Gen_Col_Value(int k,int n) { while(1) { a=color_tab[k]+1; b=m+1; color_tab[k] = a%b; if(color_tab[k]==0) return; for(j=1;j<=n;j++) { if(G[k][j] && color_tab[k]==color_tab[j]) break; } if(j==n+1) return; } } void Gr_coloring(int k,int n) { Gen_Col_Value(k,n); if(color_tab[k]==0) return; if(k==n) return; else Gr_coloring(k+1,n); }output:-
Enter the number of nodes & edges 4 5 Enter the edges of the graph Enter value of x,y 0 1 Enter value of x,y 1 2 Enter value of x,y 1 3 Enter value of x,y 2 3 Enter value of x,y 3 0 The Vertices To be Coloured As... V1:=1 V2:=2 V3:=3 V4:=1 --------------------------------
0 comments: