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

Thuật toán LDO (Largest Degree Ordering): do De Werra đề xuất năm 1990 [13]. Tương tự như SDO, LDO là một cải tiến của FF, trong đó các đỉnh được tô mầu theo thứ tự bậc của đỉnh từ lớn tới bé.

Chương trình:

#include

#include

#include

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

void in_matran(int *a,int n);

void in(int *b,int n);

int dem(int *b,int n);

int max(int *b,int n);

void up_date(int *a,int *SD,int *ToMau,int n);

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

void ToMau_SDO(int *a,int n);

int main()

{

int n,*a;

a=doc_tep(a,&n);

in_matran(a,n);

ToMau_SDO(a,n);

getch();

return 0;

}

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

{

FILE *f;

f=fopen("Graph2.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");

}

}

void in(int *b,int n)

{

printf("n");

for(int i=0;i

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

}

int dem(int *b,int n)

{

int tg=0,j;

for(int i=0;i

{

if(*(b+i)==-1)

continue;

for(j=0;j

if(*(b+j)==*(b+i))

break;

if(j==i)

tg++;

}

return tg;

}

int max(int *b,int *c,int n)

{

int tg=*b,j=0;

for(int i=j+1;i

if(*(b+i)>tg && *(c+i)==0)

{

tg=*(b+i);

j=i;

}

return j;

}

void up_date(int *a,int *SD,int *ToMau,int n,int x)

{

int *ke,j=0;

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

for(int i=0;i

*(ke+i)=-1;

for(int i=0;i

if(*(a+x*n+i)!=0 && *(ToMau+i)!=-1)

{

*(ke+j)=*(ToMau+i);

j++;

}

*(SD+x)=dem(ke,n);

}

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

{

for(int j=0;j

if((*(a+d*n+j)!=0 && j!=d) && *(c+j)==1 && *(b+j)==x)

return 0;

return 1;

}

void ToMau_SDO(int *a,int n)

{

int *ToMau,*SD,*b;

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

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

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

*ToMau=0; //To mau 0 cho dinh 1.

*b=1; //Danh dau dinh 1 da to mau.

for(int i=1;i

*(ToMau+i)=-1;

int tg;

for(int i=1;i<=n;i++)

{

for(int k=0;k

if(*(ToMau+k)==-1)

up_date(a,SD,ToMau,n,k);

tg=max(SD,b,n);

for(int j=0;j

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

{

*(ToMau+tg)=j;

*(b+tg)=1;

break;

}

}

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

for(int i=0;i

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

}
Theo lập trình vn


Posted in: Lập trình cơ bản