Контрольные вопросы

1. Дайте сравнительную характеристику аналитических способов представления графа.

Задание для лабораторной работы.

1. Написать и отладить программу в соответствии с вариантом задания. Такая программа должна содержать:

   1. ввод исходного графа из файла заданного вида и формирование для него списков инцидентности;

   2. определение и вывод количества вершин и ребер (дуг) графа, вывод списков инцидентности исходного графа;

   3. выполнение индивидуального задания варианта и вывод его результатов.

2. Продемонстрировать работу программы на контрольном примере.

3. Текст программы, граф и исходный файл контрольного примера, результаты работы программы на контрольном примере оформить в отчет.

Лабораторная работа №6 алгоритмы построения кратчайших путей в графе и кратчайшего остова графа

Цель работы: изучение алгоритмов на графах

Теоретические сведения

1. Построение кратчайшего пути между двумя вершинами.

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

Для определения кратчайших расстояний от фиксированной начальной вершины до всех вершин ориентированного графа воспользуемся алгоритмом Форда-Беллмана. Обозначим через C – матрицу весов дуг графа (вес несуществующей дуги в задачах поиска минимума расстояний считаем равным +), D – массив кратчайших расстояний от начальной вершины s до всех вершин графа (полагаем ).

{ for ( ) ; ;

for ()

for ()

for ()

}

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

Количество итераций вычисления массива D можно уменьшить, сравнивая массивы в конце текущей и предыдущей итерации (аналогично, алгоритмам сортировки). Если значения массива D не изменились на данной итерации, то вычисления заканчиваются.

Алгоритм восстановления кратчайшего пути от начальной вершины s до конечной вершины t использует механизм стека. В нём применяются следующие обозначения:

1. СТЕК– поместить вершинуv в стек;

2. СТЕК – извлечь вершину v из стека.

{ СТЕК:=; СТЕК; ;

while ( )

{ for ( )

if () СТЕК;

;

}

}

Конечная вершина пути заносится в стек, и пока верхушка стека v не совпадёт с начальной вершиной s, будет определяться предыдущая вершина пути u, т.е. вершина, на которой достигается минимум

2. Построение кратчайшего остова.

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

Для построения кратчайшего остова воспользуемся алгоритмом Краскала. Обозначим через – строящийся кратчайший остов, разбиение множества вершин остова на классы эквивалентности по отношению связанности вершин –.

Предварительно рёбра упорядочиваются в порядке возрастания весов. Обозначим ,. Вначале, разбиение содержитn компонент связности, каждая компонента связности содержит одну вершину, т.е. . Программно разбиениеможно реализовать как вектор, состоящий из множеств.

{ T:= ; ;

for ( i =) ;

for ( j = )

{ ; ;

if ( () () () )

{ ; ;

;

}

}

}

Для построения остова просматриваются все рёбра графа. Если вершины, инцидентные данному ребру, принадлежат разным компонентам связности остова (т.е. вершины принадлежат разным множествам разбиения), то ребро добавляется в остов, а его вес суммируется с весом остова. Добавление ребра в остов влечёт за собой пересчёт разбиения его множества вершин, при этом два множества разбиения объединяются. В противном случае (обе вершины принадлежат одной компоненте), добавления ребра не происходит, так как это повлечёт за собой появление цикла в графе.