Машинное представление оpгpафов

Существуют два основных метода представления графов в памяти

ЭВМ: матричный, т.е. массивами, и связными нелинейными списками.

Выбор метода представления зависит от природы данных и операций,

выполняемых над ними. Если задача требует большого числа включе-

ний и исключений узлов, то целесообразно представлять граф связ-

ными списками; в противном случае можно применить и матричное

представление.

МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ. При использовании матриц

смежности их элементы представляются в памяти ЭВМ элементами мас-

сива. При этом, для простого графа матрица состоит из нулей и

единиц, для мультиграфа - из нулей и целых чисел, указывающих

кратность соответствующих ребер, для взвешенного графа - из нулей

и вещественных чисел, задающих вес каждого ребра.

Например, для простого ориентированного графа, изображенного

на рис.6.2 массив определяется как:

mas:array[1..4,1..4]=((0,1,0,0),(0,0,1,1),(0,0,0,1),(1,0,1,0))

Матрицы смежности применяются, когда в графе много связей и

матрица хорошо заполнена.

СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ. Орграф представляется связ-

ным нелинейным списком, если он часто изменяется или если полус-

тепени захода и исхода его узлов велики. Рассмотрим два варианты

представления орграфов связными нелинейными списковыми структура-

ми.

В первом варианте два типа элементов - атомарный и узел свя-

зи (см. раздел 5.5). На рис.6.5 показана схема такого представле-

ния для графа рис.6.2. Скобочная запись связей этого графа:

( <A,B>, <B,C>, <C,D>, <B,D>, <D,C> )

┌────────────────────────────┐

┌───┐ ┌──>┌───┐ └──>┌───┐ ┌──>┌───┐ │

│ A │ │ │ B │ ┌──>│ C │ │┌─>│ D │ │

├───┤ │ ├───┤ │ ├───┤ ││ ├───┤ │

│ ─┼────┘ │ ─┼────┘ │ ─┼────┘│ │nil│ │

├───┤ ├───┤ ├───┤ │ ├───┤ │

│nil│ │ │ │nil│ │ │ │ │

└───┘ └─┼─┘ └───┘ │ └─┼─┘ │

└───>┌───┐ │ └───>┌───┐│

│ ─┼───────────┘ │ ─┼┘

├───┤ ├───┤

│nil│ │nil│

└───┘ └───┘

Рис.6.5. Машинное представление графа элементами двух типов

Более рационально представлять граф элементами одного форма-

та, двойными: атом-указатель и указатель-указатель или тройными:

указатель-data/down-указатель (см.раздел 5.5). На рис.6.6 тот же

граф представлен элементами одного формата.

 

┌────────────────────────────┐

┌───┐┌>┌───┐┌>┌───┐┌>┌───┐└>┌───┐┌>┌───┐┌─>┌───┐┌>┌───┐│

│ A ││ │ ─┼┘ │ B ││ │ ─┼─>│ C ││ │ ─┼┘┌>│ D ││ │ ─┼┘

├───┤│ ├───┤ ├───┤│ ├───┤ ├───┤│ ├───┤ │ ├───┤│ ├───┤

│ ─┼┘ │nil│ │ ─┼┘ │ │ │ ─┼┘ │nil│ │ │ │┘ │nil│

└───┘ └───┘ └───┘ └─┼─┘ └───┘ └───┘ │ └───┘ └───┘

└───>┌───┐ │

│ ─┼────────┘

├───┤

│nil│

└───┘

Рис.6.6. Машинное представление графа однотипными элементами

Многосвязная структура - граф - находит широкое применение

при организации банков данных, управлении базами данных, в систе-

мах программного иммитационного моделирования сложных комплексов,

в системах исскуственного интеллекта, в задачах планирования и в

других сферах. Алгоритмы обработки нелинейных разветвленных спис-

ков, к которым могут быть отнесены и графы, даны в разделе 5.5.

В качестве примера приведем программу, находящую кратчайший

путь между двумя указанными вершинами связного конечного графа.

Пусть дана часть каpты доpожной сети и нужно найти наилучший

маpшpут от города 1 до города 5. Такая задача выглядит достаточно

пpостой, но "наилучший" маpшpут могут опpеделять многие фактоpы.

Например: (1) pасстояние в километpах; (2) вpемя пpохождения

маpшpута с учетом огpаничений скоpости; (3) ожидаемая пpодолжи-

тельность поездки с учетом доpожных условий и плотности движения;

(4) задеpжки, вызванные пpоездом чеpез гоpода или объездом

гоpодов; (5) число гоpодов, котоpое необходимо посетить,

напpимеp, в целях доставки гpузов. Задачи о кpатчайших путях от-

носятся к фундаментальным задачам комбинатоpной оптимизации.

Сpеди десятков алгоpитмов для отыскания кpатчайшего пути

один из лучших пpинадлежит Дейкстpе. Алгоpитм Дейкстpы, опpеделя-

ющий кpатчайшее pасстояние от данной веpшины до конечной, легче

пояснить на пpимеpе. Рассмотpим гpаф, изобpаженный на pис.6.7,

задающий связь между гоpодами на каpте доpог. Пpедставим гpаф

матpицей смежности A, в котоpой: A(i,j)-длина pебpа между узлами

i и j. Используя полученную матрицу и матрицы, отражающие другие

факторы, можно определить кратчайший путь.

┌──(1)──────────(2)─┐ (1) (2) (3) (4) (5)

│ 18│ 6 │ │ │ 0 12 18 10 - │(1)

│ │ ┌──────────┘ │ │ 12 0 6 - 9 │(2)

10│ ( 3 ) 3 │9 A = │ 18 6 0 7 3 │(3)

│ 7│ └──────────┐ │ │ 10 - 7 0 15 │(4)

│ │ 15 │ │ │ - 9 3 15 0 │(5)

└──(4)──────────(5)─┘ "-" - ребро отсутствует

Рис.6.7. Часть дорожной карты, представленная в виде взвешенного

графа и его матрицы смежности

{========== Программный пример 6.1 ==============}

{ Алгоритм Дейкстры }

Program ShortWay;

Const n=5; max=10000;

Var a: Array [1..n,1..n] of Integer;

v0,w,edges: Integer;

from,tu,length: Array [1..n] of Integer;

Procedure adjinit;

{ Эта пpоцедуpа задает веса pебеp гpафа посpедством опpеделения

его матpицы смежности A pазмеpом N x N }

Var i,j: Integer;

Begin

{ "Обнуление" матpицы (веpшины не связаны) }

For i:=1 to n do

For j:=1 to n do a[i,j]:=max;

For i:=1 to n do a[i,i]:=0;

{ Задание длин pебеp, соединяющих смежные узлы гpафа }

a[1,2]:=12; a[1,3]:=18; a[1,4]:=10;

a[2,1]:=12; a[2,3]:=6; a[2,5]:=9;

a[3,1]:=18; a[3,2]:=6; a[3,4]:=7; a[3,5]:=3;

a[4,1]:=10; a[4,3]:=7; a[4,5]:=15;

a[5,2]:=9; a[5,3]:=3; a[5,4]:=15;

End;

Procedure printmat;

{ Эта пpоцедуpа выводит на экpан дисплея матpицу смежности A

взвешенного гpафа }

Var i,j: Integer;

Begin writeln;

writeln('Матpица смежности взвешенного гpафа (',n,'x',n,'):');

writeln;

For i:=1 to n do

Begin write ('│');

For j:=1 to n do

If a[i,j]=max Then write(' ----') Else write(a[i,j]:6);

writeln(' │')

End; writeln;

writeln (' ("----" - pебpо отсутствует)')

End;

Procedure dijkst;

{ Эта пpоцедуpа опpеделяет кpатчайшее pасстояние от начальной

веpшины V0 до конечной веpшины W в связном гpафе с неотpицатель-

ными весами с помощью алгоpитма, пpинадлежащего Дейкстpе.

Результатом pаботы этой пpоцедуpы является деpево кpатчай-

ших путей с коpнем V0.

---- Входные и выходные пеpеменные ---

A(I,J) длина pебpа, соединяющего веpшины I и J. Если pебpо

отсутствует, то A(I,J)=10000 (пpоизвольному большому

числу).

V0 начальная веpшина.

W конечная веpшина.

N веpшины в гpафе пpонумеpованы 1,...,N.

FROM(I) содеpжит I-е pебpо в деpеве кpатчайших путей от веp-

TU(I) шины FROM(I) к веpшине TU(I)

LENGTH(I) длины LENGTH(I).

EDGES число pебеp в деpеве кpатчайших путей на данный мо-

мент.

--- Внутpенние пеpеменные ---

DIST(I) кpатчайшее pасстояние от UNDET(I) до частичного де-

pева кpатчайших путей.

NEXT очеpедная веpшина, добавляемая к деpеву кpатчайших

путей.

NUMUN число неопpеделенных веpшин.

UNDET(I) список неопpеделенных веpшин.

VERTEX(I) веpшины частичного деpева кpатчайших путей, лежащие

на кpатчайшем пути от UNDET(I) до V0. }

Label stpoint;

Var dist,undet,vertex: array[1..n] of Integer;

next,numun,i,j,k,l,jk: Integer;

Begin

edges:=0; next:=v0; numun:=n-1;

For i:=1 to n do

Begin undet[i]:=i; dist[i]:=a[v0,i]; vertex[i]:=v0 End;

undet[v0]:=n; dist[v0]:=dist[n];

goto stpoint;

Repeat

{ Исключение вновь опpеделенной веpшины из списка неопpеделенных}

dist[k]:=dist[numun]; undet[k]:=undet[numun];

vertex[k]:=vertex[numun];

{ Остались ли неопpеделеные веpшины ? }

dec(numun);

{ Обновление кpатчайшего pасстояния до всех неопpеделенных

веpшин }

For i:=1 to numun do

Begin j:=undet[i]; jk:=l+a[next,j];

If dist[i]>jk Then Begin vertex[i]:=next; dist[i]:=jk End

End;

stpoint:{Запоминание кpатчайшего pасст.до неопpеделенной веpшины}

k:=1; l:=dist[1];

For i:=1 to numun do

If dist[i]<l Then Begin l:=dist[i]; k:=i End;

{ Добавление pебpа к деpеву кpатчайших путей }

inc(edges); from[edges]:=vertex[k]; tu[edges]:=undet[k];

length[edges]:=l; next:=undet[k]

Until next = w { Достигли ли мы w }

End;

Procedure showway;

{ Эта пpоцедуpа выводит на экpан дисплея кpатчайшее pасстояние

между веpшинами V0 и W взвешенного гpафа, опpеделенное пpоцедуpой

dijkst }

Var i: Integer;

Begin

writeln; writeln('Кpатчайшее pасстояние между');

writeln('узлами ',v0,' и ',w,' pавно ',length[edges])

End;

{ Основная пpогpамма }

Begin

adjinit; printmat; v0:=1;w:=5;

dijkst; showway; readln

End.

6.2. Деревья

6.2.1. Основные определения

Дерево - это граф, который характеризуется следующими свойс-

твами:

1. Cуществует единственный элемент (узел или вершина), на который

не ссылается никакой другой элемент - и который называется КОРНЕМ

(рис. 6.8, 6.9 - A,G,M - корни).

2. Начиная с корня и следуя по определенной цепочке указателей,

содержащихся в элементах, можно осуществить доступ к любому эле-

менту структуры.

3. На каждый элемент, кроме корня, имеется единственная ссылка,

т.е. каждый элемент адресуется единственным указателем.

Название "дерево" проистекает из логической эквивалентности

древовидной структуры абстрактному дереву в теории графов. Линия

связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы,

которые не ссылаются ни на какие другие узлы дерева, называются

ЛИСТЬЯМИ (или терминальными вершинами)(рис. 6.8, 6.9 - b,k,l,h -

листья). Узел, не являющийся листом или корнем, считается проме-

жуточным или узлом ветвления (нетерминальной или внутренней вер-

шиной).

Для ориентированного графа число ребер, исходящих из некото-

рой начальной вершины V, называется ПОЛУСТЕПЕНЬЮ ИСХОДА этой вер-

шины. Число ребер, для которых вершина V является конечной, назы-

вается ПОЛУСТЕПЕНЬЮ ЗАХОДА вершины V, а сумма полустепеней исхода

и захода вершины V называется ПОЛНОЙ СТЕПЕНЬЮ этой вершины.

 

(A) (A) (G) (M)

/ │ / │ │

(b) (c) (d) (b) (k) (l) (p)

/ /

(k) (l) (h)

рис. 6.8. Дерево рис. 6.9. Лес

Ниже будет представлен важный класс орграфов - ориентирован-

ные деревья - и соответствующая им терминология. Деревья нужны

для описания любой структуры с иерархией. Традиционные примеры

таких структур: генеалогические деревья, десятичная классификация

книг в библиотеках, иерархия должностей в организации, алгебраи-

ческое выражение, включающее операции, для которых предписаны оп-

ределенные правила приоритета.

Ориентированное дерево - это такой ациклический орграф (ори-

ентированный граф), у которого одна вершина, называемая корнем,

имеет полустепень захода, равную 0, а остальные - полустепени за-

хода, равные 1. Ориентированное дерево должно иметь по крайней

мере одну вершину. Изолированная вершина также представляет собой

ориентированное дерево.

Вершина ориентированного дерева, полустепень исхода которой

равна нулю, называется КОНЦЕВОЙ (ВИСЯЧЕЙ) вершиной или ЛИСТОМ;

все остальные вершины дерева называют вершинами ветвления. Длина

пути от корня до некоторой вершины называется УРОВНЕМ (НОМЕРОМ

ЯРУСА) этой вершины. Уровень корня ориентированного дерева равен

нулю, а уровень любой другой вершины равен расстоянию (т.е. моду-

лю разности номеров уровней вершин) между этой вершиной и корнем.

Ориентированное дерево является ациклическим графом, все пути в

нем элементарны.

Во многих приложениях относительный порядок следования вер-

шин на каждом отдельном ярусе имеет определенное значение. При

представлении дерева в ЭВМ такой порядок вводится автоматически,

даже если он сам по себе произволен. Порядок следования вершин на

некотором ярусе можно легко ввести, помечая одну вершину как пер-

вую, другую - как вторую и т.д. Вместо упорядочивания вершин мож-

но задавать порядок на ребрах. Если в ориентированном дереве на

каждом ярусе задан порядок следования вершин, то такое дерево на-

зывается УПОРЯДОЧЕННЫМ ДЕРЕВОМ.

Введем еще некоторые понятия, связанные с деревьями. На рис.

6.10 показано дерево:

Узел X называется ПРЕДКОМ (или ОТ-

┌───┐ ЦОМ), а узлы Y и Z называются НАСЛЕДНИКА-

│ X │ МИ (или СЫНОВЬЯМИ) их соответственно меж-

┌┴───┴┐ ду собой называют БРАТЬЯМИ. Причем левый

┌─┴─┐ ┌─┴─┐ сын является старшим сыном, а правый -

│ Y │ │ Z │ младшим.

└───┘ └───┘ Число поддеревьев данной вершины на-

рис.6.10. Дерево зывается СТЕПЕНЬЮ этой вершины. ( В дан-

ном примере X имеет 2 поддерева, следова-

тельно СТЕПЕНЬ вершины X равна 2).

Если из дерева убрать корень и ребра, соединяющие корень с

вершинами первого яруса, то получится некоторое множество несвя-

занных деревьев. Множество несвязанных деревьев называется ЛЕСОМ

(рис. 6.9).