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

Вначале добавить все необходимые вершины графа процедурой 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.

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

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