Thuật toán tô màu SDO

Thuật toán SDO (Saturation Degree Ordering) : do Brèlaz đề xuất năm 1979 [12]. Đây cũng là một thuật toán tô mầu tuần tự các đỉnh. SDO cải tiến FF ở chỗ các đỉnh được tô mầu không theo số thứ tự của đỉnh, mà theo thứ tự bậc SD từ lớn tới bé. Trong đó bậc SD của đỉnh x được tính bằng số mầu khác nhau đã dùng để tô cho các đỉnh kề với x.

Chương trình:

#include

#include

#include

int *doc_tep(int *a,int *n);

void in_matran(int *a,int n);

int *bac_dinh(int *a,int n);

int max(int *b,int n);

int ktra_mau(int *a,int *b,int *c,int n,int x);

void ToMau(int *a,int n);

int main()

{

int n,*a;

a=doc_tep(a,&n);

in_matran(a,n);

ToMau(a,n);

getch();

return 0;

}

int *doc_tep(int *a,int *n)

{

FILE *f;

f=fopen("Graph1.INP","r");

if(f==NULL)

{

printf("nLoi Mo Tep.");

getch();

exit(1);

}

fscanf(f,"%d",n);

a=(int *) malloc(*n**n*sizeof(int));

for(int i=0;i<*n;i++)

for(int j=0;j<*n;j++)

fscanf(f,"%d",(a+i**n+j));

fclose(f);

return a;

}

void in_matran(int *a,int n)

{

for(int i=0;i

{

for(int j=0;j

printf("%5d",*(a+i*n+j));

printf("nn");

}

}

int *bac_dinh(int *a,int n)

{

int *deg;

int *b;

b=(int *) calloc(n*n,sizeof(int));

for(int i=0;i

for(int j=0;j

if(*(a+i*n+j)!=0)

{

*(b+i*n+j)=*(a+i*n+j);

*(b+j*n+i)=*(a+i*n+j);

}

printf("n");

//in_matran(b,n);

deg=(int *) calloc(n,sizeof(int));

for(int i=0;i

for(int j=0;j

{

if(*(b+i*n+j)!=0 && i!=j)

deg[i]+=*(b+i*n+j);

if(*(b+i*n+j)!=0 && i==j)

deg[i]+=*(b+i*n+j)*2;

}

//for(int i=0;i

// printf("nBac cua dinh %d la %d.",i+1,deg[i]);

return deg;

}

int max(int *b,int n)

{

int tg=*b,j=0;

for(int i=1;i

if(*(b+i)>tg)

{

tg=*(b+i);

j=i;

}

return j;

}

int ktra_mau(int *a,int *b,int *c,int n,int d,int x) //Kiem tra mau x da to cho cac dinh ke voi dinh d chua

{

for(int j=0;j

if((*(a+d*n+j)!=0 && j!=d) && *(b+j)==x) //c[]:danh dau dinh j da to mau

return 0; //b[]

return 1;

}

void in(int *b,int n)

{

printf("n");

for(int k=0;k

printf("%5d",*(b+k));

}

void ToMau(int *a,int n)

{

int *b,*c,*deg,tg;

b=(int *) calloc (n,sizeof(int));

c=(int *) calloc (n,sizeof(int));

deg=bac_dinh(a,n);

for(int i=0;i

{

tg=max(deg,n);

printf("ntg=%d",tg);

for(int j=0;j

if(ktra_mau(a,b,c,n,tg,j)==1)

{

*(b+tg)=j;

*(c+tg)=1;

break;

}

*(deg+tg)=0;

//in(deg,n);

}

printf("nTo Mau Cho Do Thi: n");

for(int i=0;i

printf("ntDinh %d ---> Mau %d",i+1,*(b+i));

}
Theo lập trình việt


Posted in: học lập trình cơ bản, lập trình cơ bản