Волновой алгоритм построения кратчайшего пути для невзвешенного графа
АЛГОРИТМЫ НА ГРАФАХ
Цель практического занятия по данной теме - освоение идей основных алгоритмов на графах и приобретение навыков в реализации этих алгоритмов.
Общие положения
Графом (G, X) называется совокупность двух конечных множеств: множества точек, которые называются вершинами (X = {Х1,...,Хn}), и множества связей в парах вершин, которые называются дугами, или ребрами ( (Хi, Хj) Î G ) в зависимости от наличия или отсутствия направленности связи.
Ребром называются две встречные дуги (Хi, Хj) и (Хj, Хi). На графе они изображаются одной линией без стрелки. Ребро, или дуга, концевые вершины которого совпадают, называется петлей.
Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.
Две вершины, являющиеся концевыми для некоторого ребра или некоторой дуги, называются смежными. Соответственно этот граф может быть представлен матрицей смежности либо матрицей инцидентности.
В табл. 3.1 приведена матрица смежности данного графа, где строки и столбцы - это вершины , “1” - это присутствие соответствующей дуги (направление принимается от буквы, именующей столбец, к букве, именующей строку); “0” - отсутствие соединения вершин. Присутствие “1” на главной диагонали данной таблицы означает наличие петель на графе.
Матрицей инцидентности называется прямоугольная матрица с числом строк, равным числу вершин графа, и с числом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаются следующим образом: “1” ставится в случае если вершина vi, инцидентна ребру uj; “0” - в противном случае.
Вершина и ребро (дуга) называются инцидентными друг другу, если вершина является для этого ребра (дуги) концевой точкой.
Взвешенным называется граф, если задана функция веса lij на дугах графа: например lij - длина дуги (Хi, Хj). Чаще всего lij ≥ 0; можно задать lij в матричном виде
с, если (Хi, Хj) Î G
(с-конечное число): lij =
∞, если (Хi, Хj) Ï G
Пример 3.1. Ha рис. 3.1 изображен граф, имеющий четыре вершимы X = {X1, X2, X3, X4} четыре дуги (X1, X3), (X2, X1), (X2, X4), (X3, X2) и два ребра (X1, X4), (X4, X3). Для вершины X1 смежными являются вершины: X2, X3 и X4, а инцидентными - дуги (X1, X3), (X2, X1) и ребро (X3, X4).
Таблица 3.2
Рис.3.1
Для ориентированного графа определяются следующие понятия:
1 . Исход вершины G(Хj) - множество вершин Xj , таких, что (Хi, Хj) Î G.
2. Вход вершины G-1(Хj) -множество вершин Xj, таких, что (Хj, Хi) Î G.
3. Степень исхода - мощность S(Xj)= | G(Хj) | множества исхода.
4. Степень входа -мощность S-1(Xj)= | G-1(Хj) | множества входа.
Для графа (рис. 3.1) рассмотрим исходы и входы вершин X1 и Х4. Имеем
G(Х1): {X3, X4}: (X4, X3), (X1, X4) Î G; G(Х4): {X1, X3}: (X4, X1), (X4, X3) Î G. G-1(Х1) = {X2, X4}: (X2, X1), (X4, X1) Î G; G-1(Х4) = {X1, X2, X3}: (X1, X4), (X2, X4), (X3, X4) Î G;
Для тех же вершин X1 и X4 степени исхода и входа соответственно равны: S(X1) = 2; S(X4) = 2; S-1(X1) = 2; S-1(X4) = 3. Для неориентированного графа степень S(Xj)= | G(Хj) | вершины Xj равна числу ребер инцидентных ей вершин.
Кроме матрицы смежности, описанной в примере 3.1, граф может быть представлен матрицей инцидентности.
Пример 3.2. На рис.3.2 изображен граф, состоящий из четырех вершин X1, Х2, Х3, Х4 и пяти дуг. Рядом с изображением графа на рисунке изображена матрица инциденций. Таблица 3.2
Рис.3.2
Алгоритмы нахождения оптимального пути
Путь из начальной вершины хн к кончиной вершине хк - последовательность дуг, начинающаяся в вершине хн Î Х, заканчивающаяся в вершине хк Î Х, и такая, что конец очередной дуги является началом следующей: (хн, хi1)( хi1, хi2)( хi2… хik)( хik, xk) = (xн, хк).
Элементарный путь – путь, в котором вершины не повторяются.
Простой путь - путь, в котором дуги не повторяются.
Маршрут - последовательность ребер, составляющих, как и путь, цепочку.
Длина пути взвешенного графа определяется как сумма весов - его дуг. Если граф не взвешен, то можно считать веса дуг равными 1 .
Кратчайшим путем между выделенной парой вершин хн и хк называется путь, имеющий наименьшую длину среди всех возможных путей между этими вершинами.
При построении длиннейшего пути рассматриваются элементарные или простые длиннейшие пути, длиннейшие пути с заданным числом выполненных циклов. Длиннейший путь между хн и хк - путь, имеющий наибольшую длину среди всех возможных путей между этими вершинами.
Волновой алгоритм построения кратчайшего пути для невзвешенного графа
0. Вершина Xн помечается 0, остальные вершины считаются непомеченными.
1. i=i+1. Помечаются индексом i все непомеченные ранее вершины, в которых есть дуги от помеченных вершин. Если помечена вершина Хк, то выполняется п.2. Иначе, если в текущем значении индекса i оказались помеченными какие-либо вершины, то выполняется п.1. Иначе делается вывод, что пути из вершины Хн в Хк нет.
2. Обратным проходом по дугам начиная от вершины Хк выделяются те дуги, которые инцидентны выделенным вершинам и разность между весами которых равна 1.
3. При движении от вершины Хн по выделенным дугам оказывается построены все кратчайшие пути к вершине Хк.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|