ГоловнаЗворотній зв'язок

Алгоритмы структуры данных

Листинг 1. 2.

   procedure greedy (var G: GRAPH; var newclr: SET );

        begin

(1)         newclr:= ø;

(2)         for для каждой незакрашенной вершины v из G do begin

(3.1)            found:= false;

(3.2)      for для каждой вершины w из newclr do

(3.3)            if существует ребро между v и w then

(3.4)                   found:= true;        

(3.5)                      if  found =  false then begin

                                      {   v не соединена ни с одной вершиной из newclr }

(4)                                  пометить  v цветом;

(5)                                  добавить  v в newclr

                              end

                     end

            end;   {   greedy }.

Обратите внимание, что наш алгоритм работает с двумя множествами вершин. Внешний цикл (строки (2) - (5)) выполняется над множеством незакрашенных вершин графа G. Внутренний цикл (строки (3.2) - (3.4)) работает с текущим множеством вершин newclr. Оператор строки (5) добавляет новые вершины в это множество.

Существуют различные способы представления множеств в языках программирования. В темах 4 и 5 мы изучим несколько таких представлений. В этом примере мы можем представить каждое множество вершин посредством абстрактного типа LIST (Список), который можно выполнить в, виде обычного списка целых чисел, ограниченного специальным значением null (для обозначения которого мы будем использовать число 0). Эти целые числа могут храниться, например, в массиве, но есть и другие способы представления данных типа LIST, которые мы рассмотрим в теме 2.

Мы отличаем абстрактный тип данных SET от встроенного типа данных set языка Pascal.Теперь можно записать оператор for в строке (3.2) в виде стандартного цикла по условию, где переменная w инициализируется как первый элемент списка newclr и затем при каждом выполнении цикла принимает значение следующего элемента из newclr. Мы также преобразуем оператор for строки (2) листинга 1.1. Измененная процедура greedy представлена в листинге 1.3. В этом листинге есть еще операторы, которые необходимо преобразовать в стандартный код языка Pascal, но мы пока ограничимся сделанным.

 

 

6