Процедура обхода графа в ширину
Матрица смежности и матрица инцидентности. Графы Г и Г 0 можно представить в аналитической форме либо матрицей смежности A, либо матрицей инцидентности B. Для нашего конкретного неориентированного графа Г матрицы A и B выглядят следующим образом:
Матрица смежности для неориентированного графа всегда симметрична. Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1. В матрице инцидентности сумма единиц по столбцам указывает на степень вершины vi. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа Г 0 матрица A и B выглядят иначе:
В общем случае матрица смежности для ориентированного графа уже не будет симметричной. В матрице инцидентности ставится 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 — все вершины красятся в белый цвет. Обход графа в ширину Описание алгоритма Замена стека, используемого в обходе в глубину очередью 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 как посещенную и повторим шаг.
Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|