Динамическое программирование, алгоритмы на графах
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
> с вершиной u (в ориентированном графе отношение смежности несимметрично).
Путем из вершины u в вершину v длиной k ребер называют последовательность ребер графа . Часто тот же путь обозначают последовательностью вершин . Если для данных вершин u, v существует путь из u в v, то говорят, что вершина v достижима из u. Путь называется простым, если все вершины в нем различны. Циклом называется путь, в котором начальная вершина совпадает с конечной. При этом циклы, отличающиеся лишь номером начальной точки, отождествляются.
Граф называется связанным, если для любой пары его вершин существует путь из одной вершины в другую.
Если каждому ребру графа приписано какое-то число (вес), то граф называют взвешенным.
При программировании вершины графа обычно сопоставляют числам от 1 до N, где - количество вершин графа, и рассматривают . Ребра нумерую числами от 1 до M, где . Для хранения графа в программе можно применить различные методы. Самым простым является хранение матрицы смежности, т.е. двумерного массива, скажем A, где для невзвешенного графа (или 1), если и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти памяти был достаточен для хранения N2 значений, даже если ребер в графе существенно меньше, чем N2. Это не позволяет построить алгоритм со временем порядка O(N) для графов, имеющих O(N) ребер.
Этого недостатка лишены такие способы хранения графа, как одномерный массив длины N списков или множеств вершин. В таком массиве каждый элемент соответствует одной из вершин и содержит список или множество вершин, смежных ей.
Для реализации некоторых алгоритмов более удобным является описание графа путем перечисления его ребер. В этом случае хранить его можно в одномерном массиве длиной M, каждый элемент которого содержит запись о номерах начальной и конечной вершин ребра, а также его весе в случае взвешенного графа.
Наконец, при решении задач на графах, в том числе и с помощью компьютера, часто используется его графическое представление. Вершины графа изображают на плоскости в виде точек или маленьких кружков, а ребра в виде линий (не обязательно прямых), соединяющих соответствующие пары вершин, для неориентированного графа и стрелок для ориентированного (если ребро направлено из u в v, то из точки, изображающей вершину u, проводят стрелку в вершину v).
Графы широко используются в различных областях науки (в том числе в истории!!!) и техники для моделирования отношений между объектами. Объекты соответствуют вершинам графа, а ребра отношениям между объектами). Подробнее об этой структуре данных можно прочитать в [5 - 7].
3. Поиск пути между парой вершин невзвешенного графа
Пусть мы имеем произвольный граф, ориентированный или неориентированный. Если в невзвешенном графе существует путь, то назовем длиной пути количество ребер в нем. Если пути нет вообще, то расстояние считается бесконечным. Путь минимальной длины при этом называется кратчайшим путем в графе. Легко показать, что любые части кратчайшего пути также являются кратчайшими путями между соответствующими вершинами. Ведь если это не так, то есть существует отрезок кратчайшего пути, между концами которого можно построить более короткий путь, то мы можем заменить этот отрезок кратчайшего пути между вершинами u и v на более короткий, тем самым уменьшив и длину кратчайшего пути между u и v, что невозможно. Это свойство кратчайших путей позволяет решать задачу их нахождения методом динамического программирования. Покажем сначала как можно записать “волновой алгоритм” так, что задача поиска кратчайшего пути между двумя вершинами графа будет решаться за O(N2) действий.
Задача 12. Для линий метрополитена некоторого города известно, между какими парами линий есть пересадочная станция. Необходимо определить, за сколько пересадок можно добраться с линии m на линию n или сообщить, что сделать это невозможно.
Решение. Такой метрополитен удобно описывать с помощью графа, вершины которого есть линии метрополитена (а не станции!!!), а наличие ребра между вершинами i и j графа соответствует наличию пересадочной станции между линиями с номерами i и j. Представим этот граф с помощь массива множеств (переменная ss в программе), в i-м элементе этого массива содержится множество всех линий, на которые можно попасть с линии i за одну пересадку. Результат будем получать с помощью множества s, на каждом шаге алгоритма содержащего номера всех линий, на которые можно попасть с исходной линии m за k пересадок. Заметим, что если вершина n нашего графа достижима из вершины m (говорят, что они находятся в одной компоненте связности), то искомое число пересадок меньше общего количества линий nn. Так как даже если после каждой из первых nn 1 пересадок мы попадали на новую линию, то после следующей пересадки мы обязательно окажемся на какой-то из линий повторно, ведь их всего nn. Поэтому, если