Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Применение поиска в ширину




 

Массив Parent, который строится в процессе обхода графа, очень полезен для поиска кратчайших путей в графе. У всех вершин, кроме начальной, есть предок. Отношение предшествования формирует дерево поиска в ширину с корнем в начальной вершине. Вершины добавляются в очередь в порядке возрастающего расстояния(в смысле количества ребер на пути от корневой вершины до данной), поэтому дерево поиска определяет кратчайший путь от начальной вершины до любой другой вершины u Î V. Этот путь можно воссоздать, следуя по цепи предшественников от u к корню, то есть фактически в обратном направлении. Так как это направление противоположно тому, в котором фактически выполнялся проход, то после восстановления пути его нужно обратить или использовать рекурсивный метод, как показано на листинге ниже.

public void PrintPath(int v_begin, int v_end)

{

int u = Parent[v_end];

if (u == v_begin)

{

Console.Write(" {0} {1} ", u, v_end);

return;

}

else if (Parent[v_end] == 0)

{

Console.WriteLine(" Пути из {0} в {1} нет", v_begin, v_end);

}

else PrintPath(v_begin, u);

Console.Write("{0} ", v_end);

}

Листинг 4. Метод печати пути по дереву поиска в ширину

 

Другим применением поиска в ширину является выделение его компонент связности. Граф называется связным, если существует путь между любыми двумя его вершинами. Например, все компьютеры, включенные в сеть Интернет, образуют связный граф, и хотя отдельная пара компьютеров может быть не соединена напрямую, но от каждого компьютера можно передать информацию к любому другому (есть путь из любой вершины графа в любую другую). Компонентой связности неориентированного графа называется его связный подграф, максимальный по включению вершин.

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

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

 

Поиск в глубину

 

Основная идея поиска в глубину, как и следует из его названия, состоит в том, чтобы идти «вглубь» графа, пока это возможно. Просмотр начинается с некоторой начальной вершины v. Она считается «открытой». Выбирается вершина u, смежная с v, открывается, то есть помечается значением 1, и процесс повторяется с одной из вершин, смежных с u.

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

В процессе обхода графа строится дерево поиска в глубину. Вершина v, через которую открывается вершина u, является ее предком. Эта информация сохраняется в массиве Parent.

Для определения состояния вершины (неоткрытая, открытая или обработанная), как и раньше, используется массив пометок Mark. Если вершина i открыта, то Mark [ i ]=1, обработана – 2, в исходном состоянии Mark [ i ]=0. Для хранения последовательности открытых, но не обработанных вершин используется стек. Эта структура данных обеспечивает возврат к предыдущей открытой вершине.

Также с каждой вершиной связываются две метки времени: время открытия вершины time_in и время завершения ее обработки time_out, которые обладают рядом интересных свойств. Рассмотрим их на примере графа, изображенного на рисунке 12 слева. Пусть поиск в глубину начинается с нулевой вершины. На рисунке 12 справа у вершин в скобках указаны две метки времени. Фактически первая метка - это та очередность, в которой вершины графа просматривались в процессе обхода. Разница во времени обработки и открытия для вершины v дает информацию о количестве потомков этой вершины в дереве поиска в глубину. Показания часов увеличиваются на единицу при каждом входе и каждом выходе из вершины, поэтому количество потомков данной вершины будет равно половине разности между моментом завершения обработки вершины и моментом ее открытия.

Рис. 12. Порядок просмотра вершин графа при поиске в глубину

При реализации алгоритма был использован рекурсивный метод. Код приведен на листинге 5.

public class DepthFirstSearchAlgm

{ // алгоритм обхода графа "сначала вглубь"

int[] Mark; // массив пометок

int[] Parent; // массив предков

int[] time_in; // время открытия каждой вершины

int[] time_out; // время завершения обработки

int time; // переменная отсчета времени

 

public void DFS(graph g)

{// инициализация переменных

Mark = new int[g.kol_vershn];

Parent = new int[g.kol_vershn];

time_in = new int[g.kol_vershn];

time_out = new int[g.kol_vershn];

time = 0;

for (int i = 0; i < g.kol_vershn; i++)

{

Mark[i] = 0;

Parent[i] = 0;

time_in[i] = 0;

time_out[i] = 0;

}

Console.WriteLine("Вершины в порядке обхода");

DFS_traversal(g, 0);

Console.WriteLine();

}

void DFS_traversal(graph g, int v)

{// рекурсивный метод обхода

Mark[v] = 1; // v - открыта

time_in[v] = time; // время открытия вершины

time++;

Console.Write("{0} ", v);

for (int i = 0; i < g.kol_vershn; i++)

{// если вершины смежны и в i еще не были

if ((g.matr_smeznosti[v, i]!= 0)&& (Mark[i] == 0))

{

Parent[i] = v; // v - предок для i

DFS_traversal(g, i); //рекурсивный вызов

}

}

Mark[v] = 2; // вершина обработана

time_out[v] = time; //время обработки вершины

time++;

}

}

Листинг 5. Обход графа в глубину

Оценим трудоемкость алгоритма. Метод DFS_traversal вызывается ровно один раз для каждой вершины v Î V, так как он вызывается только для неоткрытых вершин и первое, что он делает – это помечает переданную в качестве параметра вершину единицей. Но для каждой вершины осуществляется просмотр и проверка на смежность всех остальных вершин. Итого O (n 2), где n – количество вершин в графе. Если использовать представление графа в виде списков смежности, то трудоемкость была бы O (n+m), где m – количество ребер.

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...