Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 5.37. Сортировка вершин по невозрастанию степеней 
void SortNumEdge(ref int[] V) 
{ 
int N = Nodes.Length; 
int L1, L2; 
for (int i = 0; i <= N - 1; i++) V[i] = i; 
for (int i = 0; i <= N - 2; i++) 
for (int j = N - 1; j >= i + 1; j--) 
3 / 23

---

188 
{ 
if (Nodes[V[j]].Edge != null) 
L1 = Nodes[V[j]].Edge.Length; 
else 
L1 = 0; 
if (Nodes[V[j - 1]].Edge != null) 
L2 = Nodes[V[j - 1]].Edge.Length; 
else 
L2 = 0; 
if (L1 < L2) 
{ 
int t = V[j]; V[j] = V[j - 1];
V[j - 1] = t; 
} 
}} 
Перед реализацией самого алгоритма, представленного в листинге 5.38, 
задаются начальные значения динамического массива порядка следования 
вершин V[i], эти элементы сортируются процедурой SortNumEdge(V), про-
цедурой SetMatr() задаются элементы матрицы смежности A[i,j], и задается 
начальное значение номера цвета k = 0. 
Листинг 5.38. Функции раскраски графа и вычисления хроматическо-
го числа 
public int SetColor() // 
переборный алгоритм за-
краски 
{ 
int N = Nodes.Length; 
int[] V = new int[N]; 
for (int i = 0; i <= N - 1; i++) 
V[i] = i; 
SortNumEdge(ref V); 
4 / 23

---

189 
ClearVisit(); SetMatr(); 
bool Ok; 
int k = 0; 
do 
{ 
Ok = false; int i = -1; 
while ((i < N - 1) && !Ok) 
Ok = !Nodes[V[++i]].visit; 
if (Ok)
{ // 
найдена неокрашенная 
VisitTrue(V[i]); // 
окрасили 
Nodes[V[i]].color = Colors[k]; 
for (i = 0; i <= N - 1; i++) 
if (!Nodes[V[i]].visit && IsBorder(V[i], 
k)) 
{ // 
не окрашена и нет соседей цвета 
k 
VisitTrue(V[i]); // 
окрашено 
Nodes[V[i]].color = Colors[k]; 
} 
k++; 
} 
} while (Ok); 
return k; 
} 
В листинге 5.39 приведен текст функции, определяющей, есть ли у i-й 
вершины смежные соседи k-го цвета.