Поиск в глубину в графе

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

Процедура DFS(a)

Пометить вершину a как пройденную

Для любого ребра (a,b)

Если вершина b не пройдена, то DFS(b)

Здесь a — некоторая вершина графа.

program poiskg;

const nmax=100;

array[1..nmax,1..nmax]of byte;

var i,j,n,start:integer;

flag:array[1..nmax] of boolean;

a: array[1..nmax,1..nmax]of byte;

procedure Init;

var i,j:longint;

begin

assign(input,'input.txt');reset(input);

assign(output,'output.txt');rewrite(output);

read(n);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

read(start); считываем начальную вершину

end;

procedure dfs(v:integer); рекурсивная процедура обхода в глубину

var j:integer;

begin

flag[v]:=false; отмечаем вершину как рассмотренную

write(v:3); выводим ее

for j:=1 to n do ищем первую вершину, в которую есть путь

if (a[v,j]<>0)and flag[j] и там мы еще не были и идем от нее

then dfs (j);

end;

begin

Init;

fillchar(flag,sizeof(flag),true); отмечаем все вершины как непройденные

dfs (start); стартуем

Close(output);

end.

графызадачи

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

Известна стоимость проезда из каждого города в каждый. Hайти наименьшую стоимость проезда из города 1 до всех остальных за время O(n²).

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

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

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

При самом бесхитростном способе хранения множества выделенных городов (в булевском векторе) добавление одного города к числу выделенных требует времени O(n). Этот алгоритм называют алгоритмом Дейкстры.

program deikstra;

const nmax=100;

var d,w:array[1..nmax] of integer; массивы расстояний до вершин и пути от

start до finish

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

u:array[1..nmax] of boolean; массив признаков рассмотрена

вершина или нет

n,i,j,t:integer;

start,finish:integer; начальная и конечная вершины

min,v:integer;

besk:integer; бесконечность

procedure out(v:longint); рекурсивный вывод пути

begin

if v=0 then exit;

out(w[v]);

write(v,' ');

end;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

besk:=high(integer) div 2; бесконечность равна high(integer) div 2

read(n); считываем количество вершин

for i:=1 to n do считываем матрицу смежности

for j:=1 to n do

begin

read(c[i,j]);

if c[i,j]=0 then c[i,j]:=besk; если ребра нет, то вес ребра равен

бесконечности

end;

read(start,finish); считываем начальную и конечную вершины

for i:=1 to n do d[i]:=besk; заполняем массив d[i] бесконечностью

d[start]:=0; расстояние от стартовой вершины до нее

самой=0

fillchar(u,sizeof(u),false); заполняем массив признаков false

for t:=1 to n do begin

min:=0; номер ближайшей вершины

for v:=1 to n do перебираем все вершины

if (not u[v]) then если вершина не просмотрена

if (min=0) or (d[v]<d[min]) и она ближайшая к вершине v

then min:=v; запоминаем ее номер

u[min]:=true; отмечаем ее как просмотренную

for v:=1 to n do пересчитываем расстояния до всех

if d[v]>(d[min]+c[min,v]) вершин в пути проходящем через

then

begin

d[v]:=d[min]+c[min,v]; вершину min

w[v]:=min; заносим вершину min в путь

end;

end;

if d[finish]=besk если расстояние до конечной вершины =besk

then write('-1') выводим -1

else иначе

begin

writeln(d[finish]); выводим расстояние до конечной вершины и

out(finish); выводим путь

end;

close(input);

close(output);

end.

графызадачи