Что такое вес вершины дерева
Термин граф вводится в дискретной математике. С частным случаем графов – деревьями – мы уже познакомились. Теперь настала очередь графов.
Граф G определяется двумя множествами – множеством вершин V и множеством пар вершин E. Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром . Если упорядочена – дугой . Граф, состоящий только из ребер называется неориентированным графом . Граф, содержащий только дуги, — ориентированным графом или орграфом .
В реальных задачах граф может отражать объекты и связи между ними. При этом двусторонние связи будут отображаться в ребра графа, а однонаправленные связи – в дуги. Примером может служить сеть автомобильных дорог города. В данном случае вершинами графа будут перекрестки, ребрами – улицы с двусторонним движением, дугами – улицы с односторонним движением.
На рисунке граф можно представить точками, соответствующими вершинам графа, линиями, соединяющими вершины и соответствующими ребрам графа, и направленными от вершины к вершине линиями, соответствующими дугам графа.
Две вершины x и y, соединенные ребром (x, y), называют смежными вершинами . Если вершины соединены дугой (x, y), то вершина x смежна вершине y, а обратной смежности нет.
Два ребра называют смежными ребрами , если они имеют общую вершину.
Ребро и любая из двух его вершин называются инцидентными .
Любому ребру или вершине может быть присвоен вес. Вес вершины – число, которое характеризует вершину, вес ребра – число, характеризующее отношение между двумя вершинами. Например, для графа автомобильных дорог вес ребра может означать длину дороги от одного перекрестка до другого.
Естественно, что если сеть автомобильных дорог или любой другой граф надо заложить в компьютер, то возникает вопрос, как хранить этот граф в памяти компьютера.
2.2. Способы представления графа в памяти
Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов, поэтому подробнее остановимся на способах представления графа.
При дальнейшем изложении будем предполагать, что вершины графа пронумерованы от 1 до N, а ребра – от 1 до M. Каждому ребру и каждой вершине сопоставлен вес – целое положительное число.
Для каждого способа хранения будем определять пространственную сложность и временную сложность следующих операций:
2.2.1. Матрица смежности
Матрица смежности это двумерный массив размером N*N:
Type TAdjacencyMatrix = array [1..N, 1..N] of Integer; Var Graph: TAdjacencyMatrix;
Пространственная сложность этого способа O(N 2 ). Временные сложности сведены в таблицу
Проверка смежности вершин x и y
Перечисление всех вершин смежных с x
Определение веса ребра (x, y)
Определение веса вершины x
Перечисление всех ребер (x, y)
Перечисление ребер, инцидентных вершине x
Перечисление вершин, инцидентных ребру s
Этот способ очень хорош, когда нам надо часто проверять смежность или находить вес ребра по двум заданным вершинам.
2.2.2. Матрица инцидентности
Матрица инцидентности это двумерный массив размером N*M:
Type TIncidenceMatrix = array [1..N, 1..M] of Integer; Var Graph: TIncidenceMatrix;
Пространственная сложность этого способа O(N*M). Временные сложности сведены в таблицу
Проверка смежности вершин x и y
Перечисление всех вершин смежных с x
Определение веса ребра (x, y)
Определение веса вершины x
Перечисление всех ребер (x, y)
Перечисление ребер, инцидентных вершине x
Перечисление вершин, инцидентных ребру s
Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».
2.2.3. Списки смежных
Списки смежных это одномерный массив размером 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 2 ). Временные сложности сведены в таблицу
Проверка смежности вершин x и y
Перечисление всех вершин смежных с x
Определение веса ребра (x, y)
Определение веса вершины x
Перечисление всех ребер (x, y)
Перечисление ребер инцидентных вершине x
Перечисление вершин инцидентных ребру s
Хранение списков в динамической памяти позволяет сократить объем расходуемой памяти, так как в этом случае не будет резервироваться место под N соседей для каждой вершины.
Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин смежных с x»
2.2.4. Перечень ребер
Списки смежных это одномерный массив размером N, содержащий список вершин смежных с данной:
Type TBranchList = array [1..M] of record Node1, Node2, Weight: Integer; end; Var Graph: TBranchList;
Пространственная сложность этого способа O(M). Временные сложности сведены в таблицу
Проверка смежности вершин x и y
Перечисление всех вершин смежных с x
Определение веса ребра (x, y)
Определение веса вершины x
Перечисление всех ребер (x, y)
Перечисление ребер инцидентных вершине x
Перечисление вершин инцидентных ребру s
Как видно из таблицы, этот способ хранения графа особенно удобен, если главная операция, которой мы чаще всего будем пользоваться, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности.
2.3. Методы поиска в графе
Существует большое число алгоритмов на графах. Все они разработаны в ответ на задачи, возникающие в реальной жизни. Многие из этих алгоритмов требуют просмотра вершин графа. Поэтому здесь особенное внимание уделяется методам поиска в графе.
Поиск в графе предполагает просмотр вершин графа, начиная с некоторой. Методы поиска в графе различаются порядком рассмотрения вершин.
2.3.1. Поиск в глубину
Поиск в глубину стремится проникнуть подальше от исходной вершины. Идея этого метода следующая. На каждом шаге метода:
Для программы понадобится булевский массив:
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;
2.3.2. Поиск в ширину
Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На 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;
2.4. Методы поиска и переборные алгоритмы
Переборные алгоритмы по сути своей тоже являются алгоритмами поиска, как правило, поиска оптимального (или возможного, или всех возможных) решения(-ий). При этом решение строится не сразу – оно конструируется постепенно. В этом случае можно вести речь о переборе вершин дерева вариантов. Вершины такого графа будут промежуточными или конечными вариантами, а ребра будут указывать пути конструирования вариантов.
Рассмотрим переборные алгоритмы, основанные на методах поиска в графе, на примере задачи нахождения кратчайшего пути в лабиринте.
Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером M*N. Элемент матрицы A[i, j]=0, если клетка (i, j) проходима. В противном случае A[i, j]=1.
Требуется найти кратчайший путь из клетки (1, 1) в клетку (M, N).
Фактически дана матрица смежности (только в ней нули заменены единицами, а единицы – нулями). Лабиринт представляет собой граф.
Вершинами дерева вариантов в данной задаче являются пути, начинающиеся в клетке (1, 1). Ребра – показывают ход конструирования этих путей и соединяют два пути длины k и k+1, где второй путь получается из первого добавлением к пути еще одного хода.
2.4.1. Перебор с возвратом
Этот метод, по-английски называемый backtracking (некоторые авторы и по-русски пишут « бектрекинг »), основан на методе поиска в глубину. С житейской точки зрения перебор с возвратом – это метод проб и ошибок («попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую»). Поскольку речь идет о переборе дерева вариантов методом поиска в глубину, то во время работы алгоритма надо хранить текущий путь в дереве. Этот путь представляет собой стек Way.
Вернемся к нашей задаче. Пусть мы находимся в некоторой клетке (в начале работы алгоритма – в начальной клетке (1, 1)). Далее
if then begin ; текущая клетка := Neighbor; end else ;
Из приведенного выше фрагмента программы ясно, почему этот метод называется перебором с возвратом . Возврату здесь соответствует операция , которая уменьшает длину Way на 1.
Перебор заканчивается, когда Way пуст и делается попытка возврата назад. В этой ситуации возвращаться уже некуда.
Way – это путь текущий, но в процессе работы нам надо хранить еще и оптимальный путь OptimalWay.
Finish := False; ; ; repeat if then begin ; текущая клетка := Neighbor; if ()and () then OptimalWay := Way; end else begin if then Finish := True else ; end; until Finish;
Заметим, что алгоритм можно усовершенствовать, если не позволять, чтобы длина Way была больше или равна длине OptimalWay. В этом случае если и будет найден какой-то вариант, он заведомо не будет оптимальным. Такое усовершенствование в общем случае означает, что как только текущий путь станет заведомо неоптимальным, надо вернуться назад. В некоторых случаях это улучшение алгоритма позволяет сильно сократить перебор.
Посмотрим работу алгоритма с указанным усовершенствованием на примере лабиринта, изображенного на рисунке (строки нумеруются снизу вверх, столбцы – слева направо). Фиксируем порядок посещения соседних клеток: левая, верхняя, правая, нижняя. В таблице будем фиксировать лишь содержимое Way и OptimalWay в моменты переходов от движения вперед к возврату назад и наоборот от возвратов назад к движению вперед.
(причина возврата: найден вариант)
Источник