Сделай Сам Свою Работу на 5

Волновой алгоритм построения кратчайшего пути для невзвешенного графа





АЛГОРИТМЫ НА ГРАФАХ

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

Общие положения

Графом (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-1j) -множество вершин Xj, таких, что (Хj, Хi) Î G.

3. Степень исхода - мощность S(Xj)= | G(Хj) | множества исхода.

4. Степень входа -мощность S-1(Xj)= | G-1j) | множества входа.

Для графа (рис. 3.1) рассмотрим исходы и входы вершин X1 и Х4. Имеем

G(Х1): {X3, X4}: (X4, X3), (X1, X4) Î G; G(Х4): {X1, X3}: (X4, X1), (X4, X3) Î G. G-11) = {X2, X4}: (X2, X1), (X4, X1) Î G; G-14) = {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 Все материалы защищены законодательством РФ.