 |
Процедура обхода графа в ширину
|
|
|
|
Матрица смежности и матрица инцидентности.
Графы Г и Г 0 можно представить в аналитической форме либо матрицей смежности A, либо матрицей инцидентности B. Для нашего конкретного неориентированного графа Г матрицы A и B выглядят следующим образом:
|
|
A(Г) = 
| B(Г) = 
|
Матрица смежности для неориентированного графа всегда симметрична. Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1. В матрице инцидентности сумма единиц по столбцам указывает на степень вершины vi. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа Г 0 матрица A и B выглядят иначе:
|
| 
|
A(Г0) = 
| B(Г0) = 
|
В общем случае матрица смежности для ориентированного графа уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и – 1, если дуга заходит в нее.
Число дуг в пути минимальной длины от вершины vi до vj называется расстоянием r (vi, vj). Если между вершинами не существует никакого пути, то расстояние равно бесконечноти: r (vi, vj) = ∞.
Алгоритмы обхода графа в ширину и глубину.
Обход графа в глубину
Описание алгоритма
Поиск в глубину (DFS, depth-first search) представляет собой классический гибкий алгоритм, который применяется для решения задачи связанности и множества других задач обработки графов. Возможны две реализации этого базового алгоритма: одна в виде рекурсивной процедуры, другая — с использованием явно заданного стека. Мы будем использовать стек магазинного типа. Применение правила LIFO (Last In First Out — последним пришел, первым обслужен), которое характеризует работу стека магазинного типа, соответствует исследованию соседних коридоров в лабиринте: из всех еще не исследованных коридоров выбирается последний из тех, с которым мы столкнулись. Словом стратегия поиска в глубину такова: идти «вглубь», пока это возможно (есть непройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной.
|
|
|
Цвет. Алгоритм поиска в глубину использует три цвета. Каждая из вершин вначале белая. Будучи обнаруженной (discovered), она становится темно серой; затем когда она будет полностью обработана (finished), то есть когда список смежных с ней вершин будет просмотрен, мы красим ее в черный цвет.
Процедура обхода графа в глубину
procedure push(const n: longint);
1 t:= t + 1;
2 stack[t]:= n;
3 visited[n]:= 1;
function pop;
1 t:= t - 1;
2 pop:= stack[t];
procedure DFS(adjMatrix: array [0..n-1] of longint);
1 for i:= 0 to n - 1 do visited[i]:= 0;
2 for i:= 0 to n - 1 do begin
3 if (visited[i] <> 1) then begin
4 t:= 0;
5 push(i);
6 flag:= false;
7 while t > 0 do begin
8 if flag then k:= pop else k:= stack[t];
9 flag:= true;
10 for i:= 0 to n - 1 do
11 if (adjMatrix[k, j] > 0) and (visited[j] <> 1) and flag then begin
12 push(j);
13 flag:= false;
14 end;
15 end;
16 end;
17 end;
Пояснения
Процедура Push
добавляет элемент в стек;
красит элемент в темно-серый цвет.
Функция Pop
удаляет элемент из стека, когда у него больше нет смежных вершин;
возвращает предпоследний элемент;
красит удаленную вершину в черный цвет.
Процедура DFS
Строка 1 — все вершины красятся в белый цвет.
Строки 2–3 — находим начальный элемент новой компоненты связанности.
Строки 4–6 — добавляем начальный элемент в стек.
Строка 7 — проверяем, есть ли в стеке элементы.
Строка 8 — проверяем, есть ли у элемента смежные вершины.
Строки 10–14 — ищем смежную с элементом k вершину и добавляем ее в стек.
Обход графа в ширину
Описание алгоритма
Замена стека, используемого в обходе в глубину очередью FIFO (First In First Out — первым пришел, первым обнаружен) приводит к другому классическому алгоритму — к алгоритму поиска в ширину (BFS, breath-first search), который используется для решения других задач обработки графов, связанных с нахождением кратчайших путей. Поиск в ширину — один из базисных алгоритмов, составляющий основу многих других. Например, алгоритм Дейкстры поиска кратчайших путей и алгоритм Прима поиска минимального покрывающего дерева могут рассматриваться как обобщения поиска в ширину. Алгоритм поиска в ширину перечисляет все достижения из начальной вершины (вершины в порядке возрастания от начальной). Словом мы идем «вширь», а не «вглубь» (сначала просматривая все соседние вершины, затем соседей соседей и т. д.)
|
|
|
Цвет. Для наглядности мы будем считать, что в процессе работы алгоритма вершины графа могут быть белыми, темно серыми и черными. Вначале они все белые, но в ходе работы алгоритма вершина может стать темно-серой, а затем — черной. Точнее, при помещении вершины в очередь вершина становится темно-серой, а при удалении черной.
Процедура обхода графа в ширину
procedure push(const n: longint);
1 queue[head]:= n;
2 head:= head + 1;
3 visited[n]:= 1;
function pop;
1 pop:= queue[tail];
2 tail:= tail + 1;
procedure BFS(adjMatrix: array [0..n-1] of longint);
1 for i:= 0 to n - 1 do visited[i]:= 0;
2 for i:= 0 to n - 1 do begin
3 if (visited[i] <> 1) then begin
4 push(i);
5 while tail <> head do begin
6 k:= pop;
7 for i:= 0 to n - 1 do
8 if (adjMatrix[k, j] > 0) and (visited[j] <> 1) then
9 push(j);
10 end;
11 end;
12 end;
Алгоритмы Дейкстры.
Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны (
(u, v) ≥ 0 для всех (u, v) 
E).
Формальное объяснение
В процессе работы алгоритма Дейкстры поддерживается множество S 
V, состоящее из вершин v, для которых δ(s, v) уже найдено. Алгоритм выбирает вершину u V\S с наименьшим d [ u ], добавляет u к множеству S и производит релаксацию всех рёбер, выходящих из u, после чего цикл повторяется. Вершины, не лежащие в S, хранятся в очереди Q с приоритетами, определяемыми значениями функции d. Предполагается, что граф задан с помощью списков смежных вершин.
Не формальное объяснение
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
|
|
|
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.
|
|
|
