nextupprevious

Next:5.11 Корневое дерево
Up:5 Выбор представления данных
Previous:5.9 Слова и предложения

5.10 Граф

Уже отмечалось, что на начальном этапе разработки алгоритма нет нужды сразу фиксировать конкретные типы данных на языке Zonnon; начальная спецификация алгоритма использует лишь операции некоторого абстрактного типа данных. Проиллюстрируем это на примере разработки алгоритма построения транзитивного замыкания графа, т.е. такого графа с множеством вершин исходного графа, что в нем существует ребро между некоторыми вершинами тогда и только тогда, когда в исходном графе указанные две различные вершины соединены путем. Предварительную спецификацию алгоритма можно записать так:

ПРОДОЛЖАТЬ:=true;
while ПРОДОЛЖАТЬ do
    Найти такие вершины $U,V,W$, что
    ЕстьРебро(G,U,V), ЕстьРебро(G,V,W) и ~ ЕстьРебро(G,U,W);
    if такие вершины найдены
    then  ДобавитьРебро(G,V,W)
    else ПРОДОЛЖАТЬ:=false
    end
end.
 

Здесь мы использовали абстрактный тип данных ГРАФ с двумя операциями: операция ЕстьРебро(G,U,V) дает значение True тогда и только тогда, когда вершины $U$ и $V$ смежны, а операция
ДобавитьРебро(G,U,V) соединяет ребром вершины $U$ и$V$.

В этой записи алгоритма сохраняются различные возможности выбора конкретных структур данных для реализации абстрактного типа ГРАФ. Например, на языке Паскаль мы могли бы взять

const N = 100;  (* Число вершин исходного графа *)
type ВЕРШИНА=integer;
        МатрСмежности=array N, N of boolean; ГРАФ= МатрСмежности;

В этом случае

procedure ЕстьРебро (var X: ГРАФ; I,J:ВЕРШИНА): boolean;
begin return X[I,J] end;

procedure ДобавитьРебро (var X: ГРАФ;I,J:ВЕРШИНА);
begin X [I,J]:= True; X [J,I]:= True end;

будут реализациями наших операций абстрактного типа. Аналогичную реализацию на основе матрицы смежности можно использовать для мульти- и псевдографов, т.е. графов с кратными дугами и петлями:

type МатрСмежности=array N, N of integer;

при которой значение $G[I,J]$ для графа $G$ равно числу ребер, соединяющих вершины $I$ и $J$ (при этом петля означает два ребра).

Другой вариант реализации графа -- использовать для представления графа матрицу инцидентности:

const N = 100; (*Число вершин исходного графа *) M=300; (*Число ребер исходного графа*)
type ВЕРШИНА=integer; РЕБРО=integer;
    МатрИнцидентности=array N, M of boolean;
    ГРАФ = МатрИнцидентности;

При такой реализации значение $G[I,J]$ для графа $G$ равно True, если вершина $I$ и ребро $J$ инцидентны.

В более общем случае, когда вершинами графа являются не целые числа, а произвольные объекты типа ТипВершины, можно использовать:

object {public, value} ГРАФ;
var {public}  Смежны: МатрСмежности;
         Вершины: array ЧислоВершин of ТипВершины
end ГРАФ;

или

object {public, value} ГРАФ;
var {public} Инцидент: МатрИнфидентности;
          Вершины:array ЧислоВершин of ТипВершины
end ГРАФ;

Если в соответствующие записи, реализующие граф, добавить поле

Ребра: array ЧислоРебер of ТипРебра,

получаем реализацию графа, ребра которого -- произвольные объекты типа ТипРебра. Следует отметить, что рассмотренные реализации применимы и для ориентированных графов. Однако для ориентированного графа определение матрицы инцидентности $MI$ видоизменяется: элемент MI[K,L] равен 1, если вершина K - начало дуги L, равен -1, если вершина K - конец дуги L, и равен 0, если вершина K и дуга L не инцидентны.

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

const NM=400; (* Суммарное число вершин и дуг, т.е. NM=N+M*)
object {public, value} ВЕРШИНА;
var {public}ПервыйПреем:integer;
    Метка:ТипВершины
end ВЕРШИНА;
object {value} ГРАФ;
var {public} ВЕРШ: array N of ВЕРШИНА;
     ПРЕЕМ: array NM of integer
end  ГРАФ;

Указанное представление характеризуется следующими свойствами:

1) список преемников любой вершины графа занимает в массиве ПРЕЕМ подряд расположенные элементы и ограничен справа нулевым элементом,

2) массив ВЕРШ[K] в поле ПервПреем содержит номер элемента массива ПРЕЕМ, с которого начинается список преемников вершины K (этот элемент массива равен нулю, если является пустым указанный список преемников).

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

const NM=400; (*Суммарное число вершин и дуг, т.е. NM=N+M*)
object {public, value} ВЕРШИНА;
var {public}ПервыйПреем, ПервПред:integer;
    Метка:ТипВершины
end ВЕРШИНА;
object {value} ГРАФ;
var {public} ВЕРШ: array N of ВЕРШИНА;
     ПРЕЕМ, ПРЕД: array NM of integer
end  ГРАФ;

Реализация списков предшественников массивом ПРЕД полностью аналогична реализации списков преемников массивом ПРЕЕМ.

Возможен также вариант представления списков предшественников и списков преемников массивами длины , при котором соответствующие списки идут в каждом массиве подряд (без нулевого элемента), но вершина дополнительно хранит два числа -- длину списка предшественников и длину списка преемников.

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

Вместе с тем, рассмотренное выше представление графа с последовательным распределением памяти под списки преемников (и списки предшественников) вершин не поддерживает операции преобразования графа, такие например, как добавить дугу. Если известно, что в процессе обработки граф будет изменяться, можно использовать представление графа, основанное на связанном распределении памяти под списки:
object {public, value} ПРЕЕМНИК;
var {public}След:ПРЕЕМНИК;
    КонВер:ВЕРШИНА
end ПРЕЕМНИК;
object {public, value} ПРЕДШЕСТВЕННИК;
var {public}След:ПРЕДШЕСТВЕННИК;
    НачВер:ВЕРШИНА
end ПРЕДШЕСТВЕННИК;
object {public, value} ВЕРШИНА;
var {public}Преем: ПРЕЕМНИК;
    Пред:ПРЕДШЕСТВЕННИК;
end ВЕРШИНА;

В этом случае операции с графом, рассмотренные ранее, будут реализованы иначе. Например, для проверки наличия дуги (аналог операции ЕстьРебро для ориентированного графа) может реализована следующим образом:

procedure ЕстьДуга(U,V : ВЕРШИНА) : boolean;
    var СМЕ : boolean; ТЕК : СПИСОК;
begin
    СМЕ := False; ТЕК := U . ПРЕЕМ;
    while (ТЕК # nil) & ~ СМЕ do СМЕ:= (ТЕК . ВЕРШ=V); ТЕК:= ТЕК . След end;
    return СМЕ
end ЕстьДуга;

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

ПерВершина(ГРАФ): ВЕРШИНА;
СледВершина(ВЕРШИНА): ВЕРШИНА;
ПервПреем(ВЕРШИНА): ПРЕЕМНИК;
ПервПред(ВЕРШИНА): ПРЕДШЕСТВЕННИК;
СледПреем(ПРЕЕМНИК): ПРЕЕМНИК;
СледПред(ПРЕДШЕСТВЕННИК): ПРЕДШЕСТВЕННИК;
УдалитьДугу(ГРАФ, ВЕРШИНА, ВЕРШИНА);
ДобавитьДугу(ГРАФ, ВЕРШИНА, ВЕРШИНА);
ДобавитьВершину(ГРАФ, ВЕРШИНА);
УдалитьВершину(ГРАФ, ВЕРШИНА);

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

Выбор подходящего внешнего или внутреннего представления данных облегчается тем, что ниже мы приводим "список готовых рецептов", т.е. перечисляем некоторые возможные альтернативы представления тех математических объектов, которые упоминаются в словаре.

Один из способов внешнего представления графа состоит в том, что каждая вершина представляется ее уникальным целым номером, а сам граф задается указанием количества вершин и перечислением всех ребер, например:

граф::= количество-вершин
список-ребер::={пробел | пробел ребро список-ребер}
ребро::= откуда пробел куда
откуда::= куда::= количество-ребер::= натуральное-число
натуральное- число::={цифра |цифра натуральное-число}

Такой способ представления удобен для графа с небольшим количеством ребер. Однако для алгоритмов обхода графов он неудобен: здесь требуется перевод во внутреннее представление. Другой способ внешнего представления -- это последовательность целых типа БИТ, состоящего из двух значений 0 и 1, которую при вводе можно переводить во внутреннее представление:

const N=20; (*Количества вершин *)
var ГРАФ: array N, N of Boolean;
procedure ВВОД;
    var X:БИТ; I, J:integer;
begin
    for I:= 1 to N do
        for J:= 1 to N do
            read(X); write(X:2); ГРАФ [I,J]:=(X=1)
        end;
        writeln
    end
end.
 

Next:5.11 Корневое дерево
Up:5 Выбор представления данных
Previous:5.9 Слова и предложения

© В.Н. Касьянов, Е.В.Касьянова,2004