Реферат: Поиск в ширину на графах

(в) добавление ребра не нарушает свойства Р, т. е. P(G)<P(G') для произвольных графов G=(F,E) и G'=(V, E'), таких что Е = Е'.

Примером такого свойства Р является существование цикла (в графе, имеющем, по крайней мере три вершины).

Теорема . Если Р — свойство графа, отвечающее условиям (а), (б), (в), то каждый алгоритм, проверяющий свойство Р (т. е. вычисляющий значение P(G) для данного графа G) на основе матрицы смежности, выполняет в худшем случае Ω(n2) шагов, где n — число вершин графа.

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

(г) P(G) = P(G') для произвольных ориентированных гра­фов G = < V, E>, G’ = < V, Е> U <v, v>>, v C V.

Более экономным в отношении памяти (особенно в случае, неплотных графов, когда m гораздо меньше n2) является ме­тод представления графа с помощью списка пар, соответствующих его ребрам. Пара <x, у> соответствует дуге <х, у>, если граф ориентированный, и ребру {х, y} в случае неориентиро­ванного графа(рис. 3). Очевидно, что объем памяти в этом случае составляет 2т. Неудобством является большое число шагов — порядка т в худшем случае, — необходимое для по­лучения множества вершин, к которым ведут ребра из данной вершины.

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

1	2
1	3
1	5
2	3
2	5
3	4
4	5
4	6
5	6

1	2
1	3
3	2
3	4
5	4
5	6
6	5

Рис.3. Списки ребер соответствующие графам на рис.1.

данных, которую мы будем называть списками инцидентности. Она содержит для каждой вершины v C V список вершин и, таких что v -> u (или v — ив случае неориентированного гра­фа). Точнее, каждый элемент такого списка является записью г, содержащей вершину г. строка и указатель г. след на сле­дующую запись в списке (г. след = nil для последней записи в списке). Начало каждого списка хранится в таблице НАЧАЛО; точнее, HAЧАЛО[v] является указателем на начало спи­ска, содержащего вершины из множества {u: v+u} ({u: v - u} для неориентированного графа). Весь такой список обычно не­формально будем обозначать 3AПИСЬ[v], а цикл, выполняю­щий определенную операцию для каждого элемента и из этого списка в произвольной, но четко установленной последователь­ности, соответствующей очередности элементов в списке, будем записывать «for u C ЗАПИСЬ [v] do ...».

Отметим, что для неориентированных графов каждое ребро {u, v} представлено дважды: через вершину v в списке ЗАПИСЬ[u] и через вершину и в списке ЗАПИСЬ[v]. Во многих алгоритмах структура графа динамически модифицируется добавлением и удалением ребер. В таких случаях полагаем, что в наших списках инцидентности элемент списка ЗАПИСЬ [u], содержащий вершину и, снабжен указателем на элемент спи­ска 3AПИCЬ[v], содержащий вершину и, и что каждый эле­мент списка содержит указатель не только к следующему эле­менту, но и к предыдущему. Тогда удаляя некоторый элемент

(б)

Рис.4. Списки инцидентности ЗПИСЬ[v], v =V, соответствующие графам на рис.1.

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

Аналогичным способом определяем для каждой вершины и неориентированного графа список ПРЕДШ[v], содержащий вершины из множества (u: u -> v).

Число ячеек памяти, необходимое для представления графа с помощью списков инцидентности, будет, очевидно, иметь по­рядок m + n. На рис.4 представлены списки инцидентности, соответствующие графам на рис. 1.

2. Анализ алгоритма.

Рассмотрим метод поиска в графе, называемый поиском в ширину (англ: breadth first search). Прежде чем описать его, отметим, что при поиске в глубину чем позднее будет посещена вершина, тем раньше она будет использована — точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не исполь­зованные вершины скапливаются в стеке. Поиск в ширину, грубо говоря, основывается на замене стека очередью. После такой модификации, чем раньше посещается вершина (поме­щается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью про­смотра сразу всех еще не просмотренных соседей этой вершины. Вся процедура поиска представлена ниже (данная процедура используется также и для просмотра графа, и в псевдокоде, описанном ниже, отсутствуют операторы, которые не используются для поиска).

1 procedure WS (v);

(*поиск в ширину в графе с началом в вершине v;

переменные НОВЫЙ, ЗАПИСЬ — глобальные *)

2 begin

3 ОЧЕРЕДЬ := Æ; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь

4 while ОЧЕРЕДЬ ¹Æ do

5 begin р<= ОЧЕРЕДЬ; посетить р;

6 for u Î ЗАПИСЬ [р] do

7 if НОВЫЙ [u] then

8 begin ОЧЕРЕДЬ <= u; НОВЫЙ [u]:=ложь

9 end