平面グラフとC++での色付けについて学んでいます。しかし、私はこの作業を行うためのアルゴリズムをインストールすることを知りません。誰か助けてくれませんか？
ここに私はあなたのためにいくつかの情報を持っています！これが私のコードです！そして、それはまだ機能が終了していません。誰かが「平面グラフ」とは何かを知っている場合は、以下のPlanar_Graph関数を修正してください。：Dどうもありがとう！：バツ
# define MAX 100
int kt[MAX];
int tk=0;
int my_array[MAX][MAX]; // Graph
FILE *f;
int n,m; //m: Edge, n: Vertex
int index[MAX];
int ke[MAX];
int Color[MAX] ; //Color Array
int colors_max;
char filename[MAX];
int input(char filename[MAX])
{
int i,j;
f = fopen(filename,"r");
if (f== NULL)
{
printf("\n Error \n");
return 1;
}
else
{
printf("File mane: %s \n",filename);
printf("Content :\n");
fscanf(f,"%d",&n);
fscanf(f,"%d",&m);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
fscanf(f,"%d",&my_array[i][j]);
printf("%d ",my_array[i][j]);
}
printf("\n");
}
return 0;
}
}
void Default()
{
for(int i=0;i<colors_max;i++)
Color[i]= i;
}
void Init()
{
filename[0]=NULL;
n = 0;
}
int Planar_Graph(int my_array[MAX][MAX],int n, int m) // This is my problem
{
/* for(int i=0;i<n;i++)
if(n>=2 && (int)(n+1)*(n-2)/(n-1)>=m)
return 1;
}
else
{
return 0;
} */
}
int max()
{
int max;
int count=0;
for(int i=0;i<n;i++)
{
count = 0;
for(int j=0;j<n;j++)
if (my_array[i][j] > 0)
count++ ;
if (max < count)
max = count;
}
return max+1;
}
void Check(int x,int y) // Check around
{
int i;
Default();
for(i=0;i<n;i++)
{
if (my_array[x][i] != -1) // if edge [x,ke[i]] is color t
Color[my_array[x][i]] = -1; // then Color[t] = 0
}
for(i=0;i<n;i++)
{
if (my_array[y][i] != -1)
Color[my_array[y][i]] = -1;
}
}
void Coloring()
{
int t;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if (my_array[i][j] > 0)
{
Check(i,j) ;
for(t=0;t < colors_max;t++)
if (Color[t] == t)
{
my_array[i][j] = t;
my_array[j][i] = t;
break;
}
}
}
void main()
{
if(input("input.txt")!=1)
{
Default();
colors_max = max() ;
Coloring();
printf("\n Result:\n\n");
Planar_Graph(my_array,n,m);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if (my_array[i][j]>0)
{
printf(" %c,%c] coloring %d \n",i + 'A',j + 'A',my_array[i][j]) ;
my_array[i][j] = -1;
my_array[j][i] = -1;
}
printf("\n") ;
}
}
}
入力ファイルの例：
10 18
0 1 0 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
1 0 0 0 1 0 1 1 0 0
1 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 1 0 1 0
0 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 0 1 1
0 0 0 0 1 1 0 1 0 1
0 0 0 0 0 0 0 1 1 0