1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <iostream>
#include <conio.h>
using namespace std;
struct graf{
int stepeni;
int color;
int number;
};
void VyvodGrafa(graf arr[22],int n);
int ProverkaCvetov(graf arr[22],int n);
void InicializaciaGrafa(graf arr[22],int n);
int main()
{
int color1[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
struct graf arr[22];
const int n(9);
int i, j;
int m[n][n]= {0, 1, 1, 1, 0, 0, 0, 1, 0,
1, 0, 0, 1, 1, 0, 0, 0, 1,
1, 0, 0, 1, 0, 1, 0, 0, 0,
1, 1, 1, 0, 1, 1, 1, 1, 1,
0, 1, 0, 1, 0, 0, 1, 0, 0,
0, 0, 1, 1, 0, 0, 0, 1, 0,
0, 0, 0, 1, 1, 0, 0, 0, 1,
1, 0, 0, 1, 0, 1, 0, 0, 1,
0, 1, 0, 1, 0, 0, 1, 1, 0};
for(i = 0; i < n; i++,cout<<endl)
for(j = 0; j < n; j++)
cout<<m[i][j]<<' ';
int versh=0,z;
InicializaciaGrafa(arr,n);//Цвета по умолчанию
//Находим степени вершин
for(int i=0; i < n; i++,versh++)
{
arr[versh].stepeni=0;
arr[versh].number=i;
for(int j=0; j < n; j++)
if( m[i][j] == 1 )
arr[versh].stepeni++;
}
//Алгоритм присвоения счетов
int x=0,t,st,flag=0,metk=0,s;
for(x=0; ProverkaCvetov(arr,n)!=0 ; x++) //Цикл по цветам
{
if(arr[x].color == 66) arr[x].color = color1[x]; //Присваиваем первый цвет
for(i=0; i < n; i++) //Цикл, который красит несмежную вершину
{
t=arr[i].number; //Номер строки матрицы смежности
flag=0;
for(j=0; j < n; j++) //Идем в строку матрицы смежности
{
if((m[t][j] == 1 && t!=j)) //Если вершина несмежна с данной вершиной
{
for(s=0; s < n; s++)
m[t][j]+=m[t][j];
if(j == arr[s].number && arr[s].color != color1[x] )
{
flag++;
}
}
if( arr[j].number == t ) metk=j;
if(flag==arr[metk].stepeni && arr[metk].color == 66 )
arr[metk].color = color1[x];
}
}
cout<<endl;
}
VyvodGrafa(arr,n);
getch();
return 0;
}
//инициализируем все цвета в структуре
void InicializaciaGrafa(graf arr[22],int n)
{
for(int s=0;s < n; s++)
{
arr[s].color=66;
}
}
//вывод результатов
void VyvodGrafa(graf arr[22],int n)
{
for(int s=0;s < n; s++)
{
cout<<arr[s].number<<"-"<<arr[s].stepeni<<"-"<<arr[s].color<<endl;
}
}
//возвращает 0, если все цвета уже присвоены
int ProverkaCvetov(graf arr[22],int n)
{
int flag2=0;
for(int xx=0; xx < n; xx++) //проверяем, все ли цвета присвоены
{
if(arr[xx].color <= 16)
++flag2;
}
if(flag2==n) return 0;
else return 1;
} |
(
