![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Создание графа
Вначале добавить все необходимые вершины графа процедурой 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.
Алгоритм поиска циклов: Наверное тебе стоит обойти граф " каким либо" способом при этом помечая вершины в которых ты был, если попадаешь в вершину, где уже побывал, то делаем вывод, что найден цикл и т.д.
|