Детализация алгоритма раскраски графа

Разработаем граф-схему алгоритма раскраски графа по описанию, представленному в разделе «Эскизный проект» с учетом определённой выше структуры программы (см. рис.10).

В граф-схеме на рис.10 использованы разработанные выше структуры данных, а также следующие дополнительные переменные:

S – множество еще не раскрашенных вершин графа;

f – текущий цвет;

b – признак отсутствия вершин, которые можно раскрасить в цвет f;

– номер текущей раскрашиваемой вершины;

i – индекс для перебора вершин.

Рис. 10

Разработка формата файла для хранения графов

При записи графа в файл будем сохранять число его вершин и матрицу их смежности. Поскольку обрабатываемые графы неориентированные и матрицы их смежности симметричны относительно главной диагонали, в файле достаточно хранить только верхнюю треугольную часть матрицы. Для уменьшения размера файлов каждое значение матрицы смежности будем кодировать 1 битом, а всю хранимую часть матрицы представим цепочкой бит. Длина цепочки для графа, содержащего n вершин, будет равна

бит,

что нетрудно проверить непосредственно по виду матрицы. Поскольку минимальная единица информации файла это байт, указанные биты цепочки будут распределены между байтами, причем номер байта не будет соответствовать номеру вершины в общем случае. Число полных байт, необходимых для хранения матрицы смежности, в таком случае составит

байт,

где скобками обозначена операция округления в сторону увеличения. Количество значащих (используемых) бит в последнем байте будет вычисляться по формуле:

бит.

На рисунке 11 дано графическое представление хранимой в файле информации (а) и формата файла (б).

Алгоритм чтения графа из файла указанного формата будет включать следующие этапы:

1. Чтение числа вершин n и проверка правильности значения.

2. Циклическое побайтовое считывание оставшейся части файла в одномерный массив, содержащий B байт.

3. Извлечение строк верхней треугольной части матрицы смежности вершин графа из указанного одномерного массива путем поразрядной обработки его элементов.

4. Доопределение матрицы смежности вершин путем симметричного отображения верхней треугольной части на нижнюю и обнуления элементов главной диагонали.

Алгоритм записи графа в файл будет содержать следующие этапы:

1. Побитовое копирование строк верхней треугольной части матрицы смежности вершин в одномерный массив из B байт.

2. Запись в файл числа вершин графа n.

3. Циклическая перезапись массива с матрицей смежности в хвост файла.

(а)

(б)

Рис. 11

РАБОЧИЙ ПРОЕКТ