Способы представления графов в памяти

Матрица смежности – это матрица n×n, где n - число вершин. Строка с номером i содержит 1 в строке с номером j, если существует дуга из вершины i в вершину j.

 

Матрица инцидентности

Матрица инцидентности имеет размер m*n, где n – количество вершин, m – количество дуг графа. Элемент матрицы, соответствующий k-дуге и i-ой вершине, равен 

o +1, если дуга выходит из вершины;

o –1, если дуга входит в вершину

o и нули во всех остальных строках.

 

Списки смежности

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

 

Этот способ представления графов является внутренней реализацией

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

вершин, а в остальных – списки исходящих из них дуг. Введем следующие

типы данных для представления графов:

Type refnode=^node;

 refarc=^arc;

 node=record {список вершин}

  id:integer; {номер вершины}

  infnode:integer; {вес}

  next:refnode; {указатель на следующую вершину в

списке}

  arclist:refarc {указатель на список дуг}

 end;

 arc=record {список дуг определенной вершины}

infarc:integer; {вес}

next:refarc; {указатель на следующую дугу, исходящую из

данной вершины}

adj:refnode {указатель на вершину, в которую ведет данная

дуга}

end;

 

Добавление вершины

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

Procedure AddNode(Var graph: refnode; n,x:integer);

Var p:refnode;

Begin new(p);

With p^ do

       Begin id:=n;

             Infnode:=x;

             Arclist:=nil;

             Next:graph

       End;

       graph:=p;

end;

 

Добавление дуги

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

Procedure AddArc(u,v:refnode; y:integer);

Var a:refarc;

Begin if u=nil or v=nil then writeln(‘Отсутствует вершина’)

    Else begin

          New(a);

          With a^ do begin

               Infarc:=y;

               Adj:=v;

               Next:=u^.arclist

           End;

     u^.arclist:=a 

end 

end;

 

Создание графа

Вначале добавить все необходимые вершины графа процедурой AddNode, а затем добавить дуги процедурой AddArc.

 

 

29) Операции над графами: поиск вершины, удаление вершины, удаление дуги, текстовый вывод графа.

Поиск вершины

Функция SerchNode в качестве входных параметров получает указатель на первую вершину графа и значение информационного поля для поиска. А на выходе выдает ссылку на искомую вершину.

 

function (head:refnode; x:integer);

begin

while (head<>nil) and (head^.infnode<>x) do

      head:=head^.next;

if head=nil then

    writeln('Вершины с таким информационным полем нет');

else

    SerchNode:=head;

end;

 

Удаление дуги

Для удаления дуги указываются две ссылки на вершины, которые эта дуга соединяет. Приведенная ниже процедура удаляет элемент из списка дуг, выходящих из вершины u, если в нем записана ссылка на вершину v. Если таких элементов несколько, то удаляется первый встретившийся. 

Procedure DeleteArc(u,v:refnode);

Var a,before:refarc;

Run:boolean;

Begin

If u<>nil then Begin

a:=u^.arclist;

run:=true;

while a<>nil and run do

  if a^.adj=v then run:=false

                  else begin

                         before:=a;

                         a:=a^.next

                         end;

if a<>nil then begin

     if a=u^.arclist then

u^.arclist:=a^.next                       

else

before^.next:=a^.next;

     dispose(a)

end

end

end;

Удаление вершины

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

Procedure DeleteNode(Var graph:refnode; v:refnode);

Var before,p,q:refnode;

a,after:refarc;

begin

 p:=graph;

 while p<>nil do {цикл по всем вершинам графа}

begin

q:=p^.next;

if p<>v then begin

 DeleteArc(p,v) {удаление дуг, направленных удаляемой

вершине}

before:=p;

end

else Begin {удаление вершины v и всех дуг, исходящих из

нее}

if p=graph then graph:=q; {если это первая вершина}

   a:=p^.arclist;

   {удаление списка дуг вершины v}

   while a<>nil do 

    begin

     after:=a^.next;

     dispose(a);

     a:=after

    end;

   if p=graph then graph:=q

   else before^.next:=q;

   dispose(p);

end;

p:=q;

 end

end;

Просмотр графа

Просмотр графа заключается в посещении всех вершин и дуг графа и

выводе в стандартный файл всей информации о графе. Для непустого графа

информация группируется по вершинам (списки смежности).

Procedure BrowseGraph(graph:refnode);

Var a:refarc;

Nn,na: integer; {счетчики количества вершин и дуг}

Begin

Nn:=0; na:=0;

while graph<>nil do begin

writeln(‘Вершина ’, graph^.id,’ с весом ’,graph^.infnode);

writeln(‘Список дуг:’);

a:=graph^.arclist;

if a=nil then writeln(‘пуст’);

while a<>nil do begin

writeln(‘Дуга к вершине ’, (a^.adj)^.id,’, вес дуги ’,a^.infarc);

na:=na+1;

a:=a^.next;

end;

nn:=nn+1;

graph:=graph^.next;

end;

writeln(‘В графе ’, nn, ‘вершин и ‘, na,’ дуг’)

end;

 

 

30) Алгоритмы поиска на графах: поиск в глубину и в ширину.

 

Поиск в глубину.

Обход в глубину (называемый иногда стандартным обходом), есть обход графа по следующим правилам:

1. Добавляет начальную вершину в стек и помечает еѐ как использованную. 

2. Рассматривает верхнюю вершину стека и добавляет в стек первую попавшуюся смежную  ей неиспользованную вершину, помечая еѐ как использованную. Если такой вершины нет,

извлекает вершину стека. 

3. Если стек не пуст, переходит к пункту 2. 3

 

Таким образом, этот алгоритм обходит все вершины, достижимые из начальной, и каждую вершину обрабатывает не более одного раза.

 

Текст процедуры обхода в глубину (рекурсивный вариант):

 

var a:array[1..nmax,1..nmax]of integer;// матрица смежности

used:array[1..nmax]of boolean; // список меток

data:array[1..nmax] of integer; //информационные поля вершин

n:integer; // количество вершин графа

procedure dfs(v:integer; search:ineger);

var

i:integer;

begin

used[v]:=true; // помещенная в стек вершина помечается использованной

for i:=1 to n do // рассматриваются все ребра, исходящие из этой вершины

// проверка, использована ли вершина, в которую ведет выбранное ребро, если да, то поиск продолжается из этой вершины.

if (a[v,i]=1)and(not used[i]) then

begin

   if data[i]=search then write('Вершина с индексом ',i)

   else

   dfs(i,search);

end;

end;

...

dfs(X,k); // здесь X - номер начальной вершины, k- информационное поле вершины.

 

Поиск в ширину.

Обход графа в ширину (breadth first search, BFS) основывается на замене стека очередью:

1. Добавляет начальную вершину в очередь и помечает еѐ как использованную. 

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

3. Если очередь не пуста, переходит к пункту 2.

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

 

procedure bfs(v:integer);

var Og:array[1..nn]of integer;

yk1,yk2:integer;

i:integer;

begin

// в элементе og[i] хранится номер группы вершины i.

Изначально номер группы всех вершин кроме стартовой равен 0, это

значит, что они ещѐ не были использованы.

for i:=1 to n do

og[i]:=0;

// Инициализация очереди, т.е. добавление в неѐ начальной

вершины с номером v

yk2:=0;

yk1:=1;

Og[yk1]:=v;

used[v]:=true; // пометка вершины использованной

while yk2 < yk1 do // цикл работает, пока очередь не пуста

begin

    inc(yk2);v:=Og[yk2];

    write(v:2);

// просматриваются все рѐбра, исходящие из первой вершины

очереди

    for i:=1 to n do

// использована ли вершина, в которую ведѐт выбранное ребро,

если нет, то вершина добавляется в очередь

       if (a[v,i] <> 0) and not used[i] then

          begin

// сдвигается указатель конца очереди

             inc(yk1);

             Og[yk1]:=i;

             used[i]:=true;

          end;

end;

end;

 

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

 

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

Дан орграф G с множеством вершин V(G). Массив w — это двумерный массив стоимостей, где элемент w[i, j] равен стоимости дуги i → j. Если дуги i → j не существует, то w[i, j] ложится равным ∞, т.е. большим любой фактической стоимости дуг. В графе выделены две вершины, s и f, начало и конец пути.

 

В общем случае может существовать несколько различных путей из s в f. С каждой вершиной v графа связана переменная l[v], называемая меткой. На каждом шаге l[v] содержит длину текущего кратчайшего особого пути к вершине v. В процессе работы метка изменяется (временная метка). Метка становится постоянной, когда найден самый короткий путь от вершины s к вершине v. Алгоритм заканчивает работу, когда постоянной становится метка от s до f. Переменная p принимает в качестве своих значений вершины графа. Н – множество вершин, имеющих временные метки.

 

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

Несложно внести изменения в алгоритм так, чтобы можно было определить сам кратчайший путь (т.е. последовательность вершин) для любой вершины. Для этого надо ввести еще один массив Р1 вершин, где P1[v] содержит вершину, непосредственно предшествующую вершине v в кратчайшем пути. В программе надо записать условный оператор с условием l[p]+w[p,v]<l[v], при выполнении которого элементу P1[v] присваивается значение p. После выполнения алгоритма кратчайший путь к каждой вершине можно найти с помощью обратного рохождения по предшествующим вершинам массива Р1.

 

Алгоритм поиска циклов:

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