Графы как структура данных

Цель работы: изучить: различные способы представления графа в памяти компьютера и методы поиска в графе (поиск в глубину и поиск в ширину);

переборные алгоритмы, основанные на методах поиска в графе.

 

Время выполнения 4 часа.

 

ЗАДАНИЕ

 

§ Разработать программу, реализующую работу с динамической структурой.

§ Произвести отладку программы путем ввода исходных данных и проверки корректности полученного результата;

§ Сделать отчет.

 

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Термин граф вводится в дискретной математике. С частным случаем графов – деревьями – мы уже познакомились. Теперь настала очередь графов.

Граф G определяется двумя множествами – множеством вершин V и множеством пар вершин E. Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром. Если упорядочена – дугой. Граф, состоящий только из ребер называется неориентированным графом. Граф, содержащий только дуги, - ориентированным графом или орграфом.

В реальных задачах граф может отражать объекты и связи между ними. При этом двусторонние связи будут отображаться в ребра графа, а однонаправленные связи – в дуги. Примером может служить сеть автомобильных дорог города. В данном случае вершинами графа будут перекрестки, ребрами – улицы с двусторонним движением, дугами – улицы с односторонним движением.

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

Две вершины x и y, соединенные ребром (x, y), называют смежными вершинами. Если вершины соединены дугой (x, y), то вершина x смежна вершине y, а обратной смежности нет.

Два ребра называют смежными ребрами, если они имеют общую вершину.

Ребро и любая из двух его вершин называются инцидентными.

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

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

Способы представления графа в памяти

Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов, поэтому подробнее остановимся на способах представления графа.

При дальнейшем изложении будем предполагать, что вершины графа пронумерованы от 1 до N, а ребра – от 1 до M. Каждому ребру и каждой вершине сопоставлен вес – целое положительное число.

Для каждого способа хранения будем определять пространственную сложность и временную сложность следующих операций:

• проверка смежности вершин x и y;
• перечисление всех вершин смежных с x;
• определение веса ребра (x, y);
• определение веса вершины x;
• перечисление всех ребер (x, y);
• перечисление ребер, инцидентных вершине x;
• перечисление вершин, инцидентных ребру s.

Матрица смежности

Матрица смежности это двумерный массив размером N*N:

Type TAdjacencyMatrix = array [1..N, 1..N] of Integer;Var Graph: TAdjacencyMatrix;

При этом

Пространственная сложность этого способа O(N²). Временные сложности сведены в таблицу

Операция	Временная сложность
Проверка смежности вершин x и y	T(1)
Перечисление всех вершин смежных с x	T(N)
Определение веса ребра (x, y)	T(1)
Определение веса вершины x	T(1)
Перечисление всех ребер (x, y)	T(N2)
Перечисление ребер, инцидентных вершине x	Номера ребер не хранятся
Перечисление вершин, инцидентных ребру s	Номера ребер не хранятся

Этот способ очень хорош, когда нам надо часто проверять смежность или находить вес ребра по двум заданным вершинам.

Матрица инцидентности

Матрица инцидентности это двумерный массив размером N*M:

Type TIncidenceMatrix = array [1..N, 1..M] of Integer;Var Graph: TIncidenceMatrix;

Пространственная сложность этого способа O(N*M). Временные сложности сведены в таблицу

Операция	Временная сложность
Проверка смежности вершин x и y	T(M*N)
Перечисление всех вершин смежных с x	T(M*N)
Определение веса ребра (x, y)	T(M*N)
Определение веса вершины x	Вес вершины не хранится
Перечисление всех ребер (x, y)	T(M)
Перечисление ребер, инцидентных вершине x	T(M)
Перечисление вершин, инцидентных ребру s	T(N)

Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».

Списки смежных

Списки смежных это одномерный массив размером N, содержащий список вершин смежных с данной:

Type TAdjacencyList = array [1..N] of record Count: Integer; {число элементов в списке} List: array[1..N] of record {список} Node, {номер смежной вершины} Weight: Integer; {вес ребра} end;; end;Var Graph: TAdjacencyList;

Пространственная сложность этого способа O(N²). Временные сложности сведены в таблицу

Операция	Временная сложность
Проверка смежности вершин x и y	T(N)
Перечисление всех вершин смежных с x	T(N)
Определение веса ребра (x, y)	T(N)
Определение веса вершины x	Вес вершины не хранится
Перечисление всех ребер (x, y)	T(M)
Перечисление ребер инцидентных вершине x	Номера ребер не хранятся
Перечисление вершин инцидентных ребру s	Номера ребер не хранятся

Хранение списков в динамической памяти позволяет сократить объем расходуемой памяти, так как в этом случае не будет резервироваться место под N соседей для каждой вершины.

Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин смежных с x»

Перечень ребер

Списки смежных это одномерный массив размером N, содержащий список вершин смежных с данной:

Type TBranchList = array [1..M] of record Node1, Node2, {пара вершин, которые связывает ведро} Weight: Integer; {вес ребра} end;Var Graph: TBranchList;

Пространственная сложность этого способа O(M). Временные сложности сведены в таблицу

Операция	Временная сложность
Проверка смежности вершин x и y	T(M)
Перечисление всех вершин смежных с x	T(M)
Определение веса ребра (x, y)	T(M)
Определение веса вершины x	Вес вершины не хранится
Перечисление всех ребер (x, y)	T(M)
Перечисление ребер инцидентных вершине x	T(M)
Перечисление вершин инцидентных ребру s	T(1)

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

Методы поиска в графе

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

Поиск в графе предполагает просмотр вершин графа, начиная с некоторой. Методы поиска в графе различаются порядком рассмотрения вершин.

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

Поиск в глубину стремится проникнуть подальше от исходной вершины. Идея этого метода следующая. На каждом шаге метода:

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

2. Если таковой нет, то возвращаемся в вершину, из которой мы попали в текущую.

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

Для программы понадобится булевский массив:

Visited: array[1..N] of Boolean;

В этом массиве будем помечать уже посещенные вершины. Первоначально массив должен быть заполнен значениями false (ни одна из вершин не была посещена). Также договоримся хранить граф в виде списков смежности.

Теперь реализуем рекурсивную логику алгоритма в рекурсивной программе (v – номер вершины):

procedure DepthSearch(v: Integer);Var j: Integer;begin Visited[v]:= True; Write(‘Вершина ’, v, ‘посещена.’); for j:= 1 to Graph[v].Count do if not Visited[Graph[v].List[j].Node] then DepthSearch(Graph[v].List[j].Node);end;

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

procedure DepthSearch2(v: Integer);Var Way: array[1..N] of record {содержимое стека возврата} Node, {номер вершины} Number: Integer; {число рассмотренных элементов списка смежности} end; Count: Integer; {размер (вершина) стека возврата} Current, j: Integer; Found: Boolean;begin Count:= 1; Way[Count].Node:= v; Way[Count].Number:= 0; Visited[v]:= True; Write(‘Вершина ’, v, ‘посещена.’); repeat Current:= Way[Count].Node; Found:= False; for j:= Way[Count].Number+1 to Graph[Current].Count do begin if not Visited[Graph[Current].List[j]] then begin Inc(Count); Way[Count].Node:= Graph[Current].List[j]; Way[Count].Number:= 0; Visited[Graph[Current].List[j]]:= True; Write(‘Вершина ’, Graph[Current].List[j], ‘посещена.’); Found:= True; Break; end; end; if not Found then Dec(Count); until Count = 0;end;

Поиск в ширину

Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На i-ом шаге будут выписаны все вершины, достижимые за i ходов, если ходом считать переход из одной вершины в другую.

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

procedure WidthSearch(v: Integer);Var Delayed: array[1..N] of Integer; {очередь} Count, {хвост очереди} Head: Integer; {голова очереди} Current, j: Integer;begin Count:= 1; Head:= 0; Delayed[Count]:= v; Visited[v]:= True; Write(‘Вершина ’, v, ‘посещена.’); repeat Inc(Head); Current:= Delayed[Head]; for j:= 1 to Graph[Current].Count do if not Visited[Graph[Current].List[j]] then begin Inc(Count); Delayed[Count]:= Graph[Current].List[j]; Visited[Graph[Current].List[j]]:= True; Write(‘Вершина ’, Graph[Current].List[j], ‘посещена.’); end; until Count = Head;end;