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

procedure dfs(v:integer);

Var

i:integer;

Begin

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

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

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

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

dfs(i);

end;

...

Dfs(X); // здесь X - номер начальной вершины

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

Пример:

Для графа указать порядок включения вершин в множество достижимых вершин, если поиск начинается с вершины v1, при обходе в первую очередь предпочтение отдается вершине с меньшим номером.
	Ответ: v1, v2, v3, v4,v5, v6, v8,v9, v7.

Задание:

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

Ответ:

Путь, полученный методом поиска в глубину, в общем случае не является кратчайшим путем из вершины v в вершину u.

Поиск количества компонент связности графа

Использование обхода в глубину для поиска компонент связности графа:

For I := 1 to N do // перебираем все вершины графа

If not Use[I] Then Begin // текущая вершина не помечена

Dfs(I); // запуск поиска в глубину

Inc(K); // увеличение числа найденных компонент связности

End;

Обход (поиск) в ширину

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

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

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

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

После такой модификации чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще не просмотренных вершин, смежных этой вершины. Таким образом, "поиск ведется как бы во всех возможных направлениях одновременно".[4]

Очередность просмотра вершин при поиске в ширину:

Пример:

Порядок включения вершин при использовании метода поиска в ширину: v₁, v₂, v₃, v₄, v₇, v₈, v₆, v₅,v₉.

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

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;

Чаще всего поиск в ширину используется для нахождения кратчайшего пути от одной вершины X до другой – Y: нужно запустить поиск в ширину из вершины X и при добавлении новой вершины в очередь смотреть, не является ли она вершиной Y. Если программа не завершит работу в условном цикле, это значит, что пути из X в Y не существует.

Задание 1

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

а) метод поиска в глубину

б) метод поиска в ширину.

Ответ:

Поиск в глубину: 1, 2, 3, 4, 6, 5.

Поиск в ширину: 1, 2, 5, 3, 4, 6.

Задание 2. Поиск начинается с вершины 2.

Ответ:

Поиск в глубину: 2, 3, 4, 6, 5.

Поиск в ширину: 2, 3, 4, 5, 6.

Не нашли, что искали? Воспользуйтесь поиском по сайту: