 |
Применение обхода в глубину
|
|
|
|
Важным свойством обхода в глубину является то, что он разбивает ребра неориентированного графа на два класса: древесные (ребра дерева поиска в глубину) и обратные. Древесные ребра можно восстановить используя отношение предок-потомок, сохраненное в массив Parent. Обратные ребра – это те ребра, которые идут от потомка к одному из предков. Все ребра неориентированного графа попадают в одну из этих категорий. На рисунке 12 справа древесные ребра нарисованы сплошной линией, а обратные пунктиром.
Если в неориентированном графе нет обратных ребер, то, значит, все ребра древесные. Следовательно, это – граф без циклов (ациклический). Модификация алгоритма так, чтобы для каждого ребра печатался его тип, предоставляется читателю в качестве упражнения.
Поиск в глубину также применяется при решении следующей задачи: имеется компьютерная сеть, состоящая из центров хранения и переработки информации. Некоторые пары центров соединены каналами. Обмен информацией между любыми двумя центрами осуществляется либо непосредственно по соединяющему их каналу, если он есть, либо через другие каналы и центры. Сеть считается исправной, если каждая пара центров в состоянии обмениваться информацией. Такой сети естественно сопоставить граф: вершины - центры, ребра - каналы сети. Тогда исправной сети будет соответствовать связный граф.
Важным понятием является надежность (живучесть) сети, под которой обычно подразумевают способность сети функционировать при выходе из строя одного или нескольких центров или (и) каналов. Ясно, что менее надежной следует считать ту сеть, исправность которой нарушается при повреждении меньшего количества элементов. Оказывается, надежность сети можно измерять на основе вводимых ниже определений.
|
|
|
Вершина v графа G называется точкой сочленения (или разделяющей вершиной), если граф G \ v имеет больше компонент связности, чем G. В частности, если G связен и v - точка сочленения, то G \ v не связен. Аналогично, ребро графа называется мостом, если его удаление увеличивает число компонент. Таким образом, точки сочленения и мосты - это своего рода «узкие местa» графа. Понятно, что концевая вершина моста является точкой сочленения, если в графе есть другие ребра, инцидентные этой вершине. У графа G, изображенного на рисунке 13, вершины 2, 3, 5, 6 – точки сочленения, ребро {3, 5} является мостом.
Рис. 13. Граф G
Возвращаясь к рассмотренной выше сети, нетрудно заметить, что мостам и точкам сочленения отвечают наиболее уязвимые места сети. Для их определения используется модифицированный алгоритм поиска в глубину.
Как уже говорилось выше, алгоритм поиска в глубину в процессе работы строит дерево. В дереве поиска в глубину ребро { v, w } является мостом тогда и только тогда, когда не существует обратное ребро, которое соединяет одного из потомков w с каким-нибудь предком v. Действительно, если такое ребро существует, то { v, w } не может быть мостом. С другой стороны, если { v, w } не мост, то в графе должен быть другой путь из v в w, отличный от этого ребра. Понятно, что каждый подобный путь должен содержать одно из обратных ребер от потомков w к предкам v.
Для определения точек сочленения будем использовать очередность просмотра вершин в процессе поиска в глубину, которая записывается в массиве time_in. Если ребро { v, u } – обратное, и v не предок u, то информацию о том, что time_in [ v ] больше time_in [ u ], можно использовать для пометки вершин v и u как вершин, принадлежащих одной компоненте двусвязности. Введем массив LowDFS и будем помечать вершины графа, принадлежащие одной компоненте двусвязности, одним значением метки в этом массиве. Первоначальное значение метки совпадает со значением соответствующего элемента массива time_in. При нахождении обратного ребра { v, u } будем изменять значение метки вершины v: LowDFS [ v ] = Min (LowDFS [ v ], time_in [ u ]), так как эти вершины из одной компоненты двусвязности. Кроме того необходимо добавить смену значения метки у вершины v ребра{ v, u } на выходе из просмотра в глубину в том случае, если значение метки вершины u меньше, чем метка вершины v (LowDFS [ v ] = Min(LowDFS [ v ], LowDFS [ u ])).
|
|
|
Если для некоторой вершины u значение в массиве LowDFS [ u ] не меньше времени открытия этой вершины, то она является точкой сочленения. Также начальная вершина тоже будет точкой сочленения, если у нее не меньше двух независимых потомков.
Модифицированный код поиска в глубину приведен в листинге 6.
void DFS_traversal(graph g, int tek_vna)
{// рекурсивный метод обхода
int u;
int kids = 0; // количество потомков
bool art = false; // флаг точки сочленения
Mark[tek_vna] = 1;
time++;
LowDFS[tek_vna] = time;
time_in[tek_vna] = time; // время открытия вершины
for (u = 0; u < g.kol_vershn; u++)
{// если вершины смежны
if (g.matr_smeznosti[tek_vna, u]!= 0)
{
if(u == Parent[tek_vna]) continue;
if(Mark[u] == 0) // если вершина u неоткрытая
{
Parent[u] = tek_vna; // tek_vna - предок для u
DFS_traversal(g, u); //рекурсивный вызов
LowDFS[tek_vna] = Math.Min(LowDFS[u], LowDFS[tek_vna]);
if (LowDFS[u] >= time_in[tek_vna])
{
art = true;
}
kids++;
if (LowDFS[u] == time_in[u])
{
Console.WriteLine("{0} {1}- мост ", tek_vna, u);
}
}
else // вершина u - открытая
{ // корректируем значения массива LowDFS
LowDFS[tek_vna] = Math.Min(LowDFS[tek_vna],time_in[u]);
}
}
}
Mark[tek_vna] = 2; // вершина обработана
if (Parent[tek_vna] == -1)
art = (kids >= 2);
if (art)
Console.WriteLine(" v = {0} - точка сочленения ", tek_vna);
}
Листинг 6. Поиск мостов и точек сочленения в графе.
Похожий алгоритм для ориентированных графов принадлежит Тарьяну. Подробнее о нем можно прочитать в [3].
Упражнения.
1. Модифицировать алгоритм поиска в глубину так, чтобы для каждого ребра печатался его тип – древесное или обратное.
2. Ориентированный граф G = (V, Е) называется полусвязным, если для всех пар вершин u, v Î V, либо существует путь из u в v, либо путь из v в u, либо и то, и другое одновременно. Разработайте эффективный алгоритм для определения, является ли данный граф G полусвязным. Докажите корректность разработанного алгоритма и проанализируйте время его работы.
|
|
|
3. N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i, j), 1≤ i < j ≤ N (шестеpня с номеpом i находится в зацеплении с шестеpней j). Можно ли повеpнуть шестеpню с номеpом 1?
Если да, то найти количество шестеpен, пpишедших в движение.
Если нет, то тpебуется убpать минимальное число шестеpен так, чтобы в оставшейся системе пpи вpащении шестеpни 1 во вpащение пpишло бы максимальное число шестеpен. Указать номеpа убpанных шестеpен (если такой набоp не один, то любой из них) и количество шестеpен, пpишедших в движение.
4. Имеется N человек и прямоугольная таблица А[1: N,1: N ]; элемент A [ i, j ] равен 1, если человек i знаком с человеком j, А[ i, j ] =А[ j, i ]. Можно ли разбить людей на 2 группы, чтобы в каждой группе были только незнакомые люди.
5. Сильно связанная компонента ориентированного графа G (V, E) – это максимальное множество вершин V ’ 
V, такое что для каждой пары вершин u, v Î V’ существуют пути из u в v и из v в u. Разработайте на основе поиска в глубину алгоритм выделения всех сильно связанных компонент ориентированного графа.
Как может измениться количество сильно связных компонентов графа при добавлении в граф нового ребра?
Кратчайшие пути
Задача о поиске кратчайшего пути довольно часто встречается на практике. Например, водителю нужно проехать из Ярославля в Мурманск и у него есть дорожный атлас с указанием расстояний между каждой парой пересечений дорог. Как найти кратчайший путь? Эта задача легко решается с помощью аппарата теории графов.
Итак, пусть дан граф G = (V, E), ребрам(или дугам в случае ориентированного графа) которого приписаны веса (стоимости), задаваемые взвешенной матрицей смежности A. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s Î V (G) до заданной конечной вершины t Î V (G), при условии, что такой путь существует, то есть вершины s и t принадлежат одной компоненте связности.
Веса (стоимости), приписанные ребрам, могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в графе не было циклов с суммарным отрицательным весом. Если такой цикл все же существует и u —некоторая его вершина, то, двигаясь от s к u, обходя затем этот цикл достаточно большое число раз и попадая наконец в t, получим путь со сколь угодно малым весом. Таким образом, в этом случае кратчайшего пути не существует.
|
|
|
Поэтому будем предполагать, что все циклы в G имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.
Алгоритм Дейкстpы
Алгоритм Дейкстры (1959 г.) находит кратчайшие пути от заданной начальной вершины v_begin до всех остальных вершин графа. Основная идея этого алгоритма: на каждом шаге пытаемся уменьшить кратчайшее расстояние до непросмотренных вершин, используя очередную вершину, длину пути к которой уменьшить уже нельзя. А именно: допустим, что кратчайший путь от вершины v_begin к некоторой вершине u графа G проходит через промежуточную вершину y. Очевидно, что этот путь должен содержать кратчайший путь от v_begin к y, так как в противном случае можно было бы уменьшить длину пути от v_begin к u за счет выбора более короткого пути от v_begin к y. Таким образом, сначала надо найти кратчайший путь к вершине y.
Для достижения этой цели определяется множество непросмотренных вершин. Первоначально в нем содержатся все вершины графа, кроме начальной. На каждом шаге из этого множества выбирается та из вершин, расстояние до которой от начальной меньше, чем для других оставшихся вершин. Текущие кратчайшие расстояния от v_begin до соответствующей вершины хранятся в массиве Distance. Далее пробуем с помощью ребер выбранной вершины v_min уменьшить длину пути до оставшихся непросмотренными вершин. Если это удается, то массив Distance корректируется. Алгоритм Дейкстры также использует массив parent, который содержит номера вершин - элемент parent [ k ] есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k -ю.
Код алгоритма представлен в листинге 7. Здесь предполагается, что в граф задан взвешенной матрицей смежности. Матрица расстояний matr является копией взвешенной матрицы смежности графа, только если дуги(ребра) не существует, то вместо нуля в соответствующую ячейку записывается большое число, равное «машинной бесконечности».
public class DijkstraAlgm
{ // Алгоритм Дейкстры поиска кратчайшего расстояния от
// вершины v_begin до остальных вершин графа g
int[] Distance; // массив расстояний от начальной вершины
int[] parent; // массив предков на кратчайшем пути
public DijkstraAlgm(graph g, int v_begin)
{
Distance = new int[g.kol_vershn];
|
|
|
parent = new int[g.kol_vershn];
int[,] matr = new int[g.kol_vershn, g.kol_vershn];
// инициализация
for (int i = 0; i < g.matr_smeznosti.GetLength(0); i++)
for (int j = 0; j < g.kol_vershn; j++)
{
matr[i, j] = g.matr_smeznosti[i, j];
if (g.matr_smeznosti[i, j] == 0)
matr[i, j] = int.MaxValue;
}
//множество непросмотренных вершин
HashSet<int> mnvo_vn = new HashSet<int>();
for (int i = 0; i < g.kol_vershn; i++)
{
mnvo_vn.Add(i);
// инициализация массива расстояний
Distance[i] = matr[v_begin, i];
if (Distance[i] < int.MaxValue)
parent[i] = v_begin;
}
Distance[v_begin] = 0;
parent[v_begin] = -1;
mnvo_vn.Remove(v_begin);
// основной цикл
while (mnvo_vn.Count!= 0)
{
// ищем вершину из мн-ва с мин. расстоянием
int min_d = int.MaxValue; // мин. расстояние
int v_min = -1; // номер выбранной вершины
foreach (int u in mnvo_vn)
{
if (Distance[u] < min_d)
{
min_d = Distance[u];
v_min = u;
}
}
// удаляем найденную вершину из мн-ва непросмотренных в-н
if (v_min!= -1)
mnvo_vn.Remove(v_min);
// пересчитываем расстояния
foreach (int u in mnvo_vn)
{
if (matr[v_min, u] < int.MaxValue)
{
Distance[u] = Math.Min(Distance[u],
Distance[v_min] + matr[v_min, u]);
if (Distance[u] == (Distance[v_min] + matr[v_min, u]))
{
parent[u] = v_min;
}
} }
} // к основному циклу
Console.WriteLine(" Расстояния от вершины {0} до ", v_begin);
for (int i = 0; i < g.kol_vershn; i++)
{
Console.WriteLine("{0} = {1} ", i, Distance[i]);
}
}
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;
}
PrintPath(v_begin, u);
Console.Write("{0} ", v_end);
}
}
Листинг 7. Алгоритм Дейкстры
Трудоемкость алгоритма Дейкстры равна O (n2). Рассмотрим работу алгоритма на примере взвешенного ориентированного графа, изображенного на рисунке 14.
 |
Рис. 14. Взвешенный орграф
| Номер шага | Мн-во непросм. вершин | Тек. вершина | Distance | Parent | |||||||
| {1, 2, 3, 4} | - | ∞ | ∞ | -1 | -1 | -1 | |||||
| {2, 3, 4} | ∞ | -1 | -1 | ||||||||
| {2, 4} | -1 | ||||||||||
| {4 } | -1 |
После выполнения алгоритма кратчайший путь к каждой вершине можно найти с помощью обратного прохождения по предшествующим вершинам массива Рarent.
Приведем неформальное доказательство корректности алгоритма: на каждом шаге выбирается еще непросмотренная вершина v_min, расстояние до которой от начальной вершины наименьшее из всех необработанных вершин. Затем при помощи дуг (ребер) вершины v_min уменьшается, если это возможно, расстояние до непросмотренных вершин. Очевидно, длину пути до тех вершин, которые уже просмотрены, уменьшить нельзя (действительно, для всех u, где u – уже просмотренная вершина, имеем Distance [ u ] < Distance [ v_min ] + matr [ u, v_min ], так как Distance [ u ] < Distance [ v_min ] – по правилу выбора очередной вершины в алгоритме, а все дуги имеют неотрицательный вес).
Далее, предположим для выбранной вершины длина пути не минимальна. Тогда существует путь с суммарным весом меньше, чем Distance [ v_min ]. Обозначим за y – предпоследнюю вершину в этом пути. Получили, что Distance [ v_min ] > Distance [ y ] + matr [ y, v_min ], что противоречит шагу алгоритма.
Заметим, что если требуется построить путь от начальной вершины, только до одной конечной, то при исключении конечной вершины из множества еще непросмотренных вершин, можно завершать работу алгоритма.
|
|
|
