1.3. Задание на выполнение
Написать программу по заданному варианту. Ввод данных выполнить с клавиатуры или из текстового файла. Предусмотреть ошибки ввода – некорректные данные, отсутствие файла и т.д..
Практическое занятие № 5. «Построение матрицы достижимости»
1.1. Цель работы
Реализовать алгоритмы построения матрицы достижимости.
1.2. Основные определения
М
если вершина
достижима
из
;
,
элементы которой задаются по правилу
1.10:
если вершина
не достижима
из
;
1.3. Алгоритмы получения матрицы достижимости
1.3.1. Алгоритм построчного сложения
Пусть граф G=(X,U), задан матрицей смежности А. Получим матрицу достижимости D графа следующим способом:
1. D = A;
2. Цикл (
)
2.1. Пока (в строке i существует хотя бы одна
не просмотренная 1)
2.1.1. Если (
)
То прибавить к строке i
строку j.
2.2. Конец цикла
3. Конец цикла
4. Печать D
5. Конец
1.3.2. Алгоритм булевого сложения матриц
Пусть граф G=(X,U), задан матрицей смежности А. Получим матрицу достижимости D графа следующим способом:
1.
;
// E
– единичная
матрица
2.
3.
4. i=1;
5. Пока (
)
5.1.
5.2. i =i+1
5.3.
6. Конец цикла
7. Конец
1.4. Задание на выполнение
Граф задан матрицей смежности. Найти матрицу достижимости графа.
Практическое занятие № 6. «Алгоритмы на графах»
1.1. Цель работы
Программная реализация основных алгоритмов на графах
1.2. Алгоритмы обходов графа
Дан граф G=(X,U), .
1. Цикл ( )
1.1. M[ ]=0; // Все вершины не отмечены
2. Конец цикла
3. Выбрать произвольную
вершину
4.
// Записать выбранную вершину в структуру
Т
5.
//
Отмечаем вершину, как пройденную
6. Пока (T не пуста)
6.1.
// извлекаем вершину из структуры
6.2. Печать u
6.3. Цикл(для всех вершин w, смежных с u)
6.3.1. Если (M[w]=0)
То
;
M[w]=1
6.4. Конец цикла
7. Конец цикла
8. Конец
Если структуру T определить как стек, то алгоритм обхода будет выполняться «в глубину». Если же Т определена как очередь, будет выполняться обход «в ширину».
1.3. Алгоритмы поиска путей на графах
1.3.1. Алгоритм Дейкстры
Алгоритм Дейкстры находит кратчайший путь между двумя заданными вершинами в орграфе.
Дан граф G=(X,U), . Граф задан матрицей весов C, s– начальная вершина обхода, t – конечная вершина обхода.
На выходе алгоритма создаются два массива:
Т – если вершина v лежит на кратчайшем пути, то T[v]- длина кратчайшего пути от s к v.
H – H[v] – вершина, непосредственно предшествующая v на кратчайшем пути.
1. Цикл(
)
1.1. T[x]=
//
кратчайший
путь не известен
1.2. M[x] = 0 // все вершины не отмечены
2. Конец цикла
3. H[s]=0 // s ничего не предшествует
4. T[s]=0 // кратчайший путь имеет длину 0
5. M[s] = 1 // вершина s пройдена
6. v = s // зафиксируем текущую вершину
7. Цикл (1)
7.1. Цикл(для
смежных
с v)
7.1.1. Если (M[u]==0 и T[u]>T[v]+C[v,u])
То T[u]>T[v]+C[v,u]; // найден более
// короткий путь из s в u через v
H[u]=v;
7.2. Конец цикла
7.3. t=
7.4. v=0
7.5. Цикл( )
7.5.1. Если (M[x]==0 и T[x]<t)
То v=u; t=T[u] // вершина v заканчивает
// кратчайший путь из s.
7.6. Конец цикла
7.7. Если (v==0) То «Нет пути из s в t»; Закончить выполнение цикла.
7.8. Если (v==t) То «Путь найден»;
Печать Т[t];
Печать Н[t].
7.9. M[v]=1
8. Конец цикла
9. Конец
1.3.2. Алгоритм Форда
Алгоритм Форда позволяет найти расстояние от заданной вершины s до всех вершин T[v]=d(s,v), ориентированного графа. Исходными данными для этого алгоритма является матрица весов дуг С. В отличие от алгоритма Дейкстры алгоритм может быть использован на графах с отрицательными длинами дуг.
Дан граф G=(X,U), . Граф задан матрицей весов C. s – вершина начала пути.
1. Цикл (для всех вершин x графа G)
1.1. D[x]:=C[s,x];
2. Конец цикла
3. D[s]:=0;
4. Цикл (
)
// последовательно перебрать все ребра
4.1. Цикл (для всех
вершин v
графа,
v
)
// применить процесс поиска кратчайшего
//пути для всех ребер
4.1.1. Цикл (для всех
вершин u
графа, u
)
4.1.1.1 Если (D[v]>D[u]+C[u,v])
То D[v]=D[u]+C[u,v]
4.1.2. Конец цикла
4.2. Конец цикла
// закончить алгоритм досрочно
5. Если нет изменений в D, То k=n-2
6. Конец цикла
7. Печать D.
8. Конец
1.3.4. Алгоритм ближайшего соседа
Существует другой метод получения кратчайшего остовного дерева, который не требует ни сортировки ребер, ни проверки на цикличность на каждом шаге, - так называемый алгоритм ближайшего соседа. Просмотр начинается с некоторой произвольной вершины a в заданном графе. Пусть (a,b)- ребро с наименьшим весом, инцидентное a; ребро (a,b) включается в остов. Затем среди всех ребер, инцидентных либо a, либо b, выбираем ребро с наименьшим весом и включаем его в частично построенное дерево. В результате этого в дерево добавляется новая вершина, например, c. Повторяя процесс, ищем наименьшее ребро, соединяющее a, b или c с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из G не будут включены в дерево, то есть пока дерево не станет остовным.
Дан граф G=(X,U), . Граф задан матрицей весов C.
1. T – пустое множество ребер остовного дерева
2. а – произвольная вершина графа
3.
4. Пока (
)
4.1. Найти ребро
(u,v)
с минимальным весом, такое, что
.
4.2.
5. Конец цикла
6. Печать Т
7. Конец
1.3.5. Алгоритм Краскала
Алгоритм Краскала относится к семейству «жадных» алгоритмов. Алгоритм ищет кратчайший остов в связном графе G=(X,U), . Граф задан списком ребер U с длинами. На выходе алгоритма создается список Т ребер кратчайшего остова.
1. T – пустой список
2. Упорядочить список U в порядке возрастания длин
3. k = 1 // номер рассматриваемого ребра
4. Цикл(
)
4.1. Пока (добавление ребра E[k] образует цикл в T)
4.1.1. k=k+1
4.2. Конец цикла
4.3.
5. Конец цикла
6. Печать Т
7. Конец
1.3.6.Волновой алгоритм
Волновой алгоритм является алгоритмом поиска кратчайшего пути между двумя вершинами в неориентированном ненагруженном графе.
Пусть дан граф
G=(X,U),
.
Вершина а
– начало
пути, вершина b
– конец
пути. Запишем вершину а
во фронт
волны нулевого уровня
.
Введем переменную i
=0. Далее
найдем все вершины, смежные вершинам
и ранее не пройденные. Запишем эти
вершины во фронт волны следующего уровня
.
Увеличим i
- i
= i
+1. Если среди
найденных вершин есть вершина b,
то длина
кратчайшего пути найдена и равна i,
если нет, то процесс продолжается до
тех пор пока не будет найдена конечная
вершина пути, либо, пока не будут
просмотрены все вершины графа. В этом
случае пути из a
в
b
нет.
1. Цикл( )
1.1.
// отметим все вершины, как не пройденные
2. Конец цикла
3. M[a]=0; // вершина пройдена
4. i=1
5.
6. Пока (
И
)
6.1. Цикл (для вершин
и смежных
вершинам
)
6.1.1.
6.1.2.
6.2. Конец цикла
7. Конец цикла
8. Если
То
«Путь найден», длина пути равна i-1.
Иначе «Путь не существует»
9. Конец
1.3.7. Алгоритм Уоршалла
Алгоритм вычисления транзитивного замыкания для орграфа G=(X,U), . Граф задан матрицей смежности.
1. S = R // вспомогательная матрица
2. Цикл( )
2.1. Цикл(
)
2.1.1. Цикл(
)
// вычисление
//матрицы
// транзитивного
// замыкания
2.2. Конец цикла
3. Конец цикла
4. Печать T.
5. Конец
1.3.8. Алгоритм построения эйлеровой цепи
Если граф имеет цикл содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то такая цепь называется эйлеровой цепью, а граф называется полуэйлеровым графом.
Для того, чтобы в графе существовал эйлеров цикл граф должен быть связанным, для неориентированных графов число ребер в каждой вершине должно быть четным.
Дан эйлеров граф G=(X,U), , заданный структурой смежности. Г[v]- множество вершин, смежных с вершиной v.
1. S – пустой стек //стек для хранения вершин
2.
Выбрать произвольную вершину x
3.
// положить x
в стек
4. Пока (Стек не пуст)
4.1.
4.2.
4.3. Если Г[v]- пустое множество То ; Печать v
Иначе
взять u
Г[v];
// взять первую
// вершину, смежную v
//удалить ребро (v,u)
Г[v]:=Г[v]\u;
Г[u]:=Г[u]\v;
Конец цикла
Конец