1. (Начальная установка.) Предположим, что в графе имеется числовершин вершин, что переменная старшийцвет содержит номер старшего из уже использованных цветов, а нуль показывает, что вершина еще не наделена цветом. Для всех вершин n установить цвет[n] равным нулю (т. е. сделать все вершины нераскрашенными). Установить старшийцвет равным нулю, а переменную равной единице.
2. (Основной цикл.) Пока текущаявершина не превзойдет числовершин, выполнять шаги с 3-го по 7-й. Этим шагом начинается цикл, который повторяется, пока не будут раскрашены все вершины. Перед началом каждого прохождения цикла все вершины от 1 до текущаявершина — 1 правильно раскрашены в старшийцвет цветов.
3. (Подготовка одного узла.) Увеличить цвет[текущаявершина] на единицу. Установить булеву переменную флагцикла равной значению отношения цвет[текущаявершина] <= старшийцвет. Теперь рассматриваемая вершина имеет ненулевой цвет, и необходимо проверить, совместима ли текущаявершина со своими соседями. Заметьте, что впервые добавляемая вершина всегда имеет нулевой цвет. Прибавляя единицу к нулю, мы наделяем вершину допустимым цветом. Пока цикла имеет значение истина, выполнять шаги 4 и 5.
4. (Проверка цвета смежных вершин.) Присвоить переменной флагцикла значение ложь и установить i равным единице. Пока i меньше, чем текущаявершина, выполнять шаг 5.
5. (Проверка цвета каждого соседа.) Если вершина i и текущаявершина связаны (т. е. если связь(i, текущаявершина) имеет значение «истина») и если цвет[i] и цвет[текущаявершина] равны, значит, текущаявершина имеет недопустимый цвет. В этом случае установить значение i равным текущаявершина, чтобы прервать цикл, начинающийся в шаге 4, увеличить цвет[текущаявершина] на единицу чтобы попробовать следующий цвет, и установить значение флагцикла равным значению отношения цвет[текущаявершина] <= старшийцвет. В противном случае просто увеличить i на единицу, чтобы проверить следующего соседа. Заметьте, что последнее присваивание переменной флагцикла перекроет присваивание в шаге 4, но может установить переменную флагцикла равной значению ложь. Далее, если начинающийся в шаге 4 цикл завершается нормально (т. е. без насильственного присваивания переменной текущаявершина значения i), произойдет выход из цикла, начинающегося в шаге 3. Важно, чтобы при проверке допустимости раскраски использовались лишь вершины, номера которых строго меньше, чем текущаявершина, поскольку вершины с большими номерами еще не раскрашены.
6. (Продвинуться или вернуться?) Если текущаявершина получила допустимый цвет, мы хотим перейти к следующей вершине; в противном случае необходимо отступить. Поэтому, если цвет [текущаявершина] > старшийцвет, установить цвет [текущаявершина] равным нулю и уменьшить значение текущаявершина на единицу; в противном случае увеличить значение текущаявершина на единицу. Заметьте, что цвета вершин с номерами большими, чем текущаявершина, по-прежнему нулевые и что, когда мы возвращаемся к уже раскрашивавшейся вершине, мы продолжаем продвигать ее цвет со значения, оставшегося от предыдущей обработки.