Графы. Деревья Продолжение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов Граф (Л.Н.Толстой) Граф (не ориентированный) Граф (ориентированный) - презентация

1 Графы. Деревья Продолжение А.Г.Баханский © Программирование – вторая грамотность. А.П.Ершов Граф (Л.Н.Толстой) Граф (не ориентированный) Граф (ориентированный)

2 Оглавление Основные задачи на графах поиск каркаса минимального веса в графе (алгоритм Краскала) поиск кратчайшего пути в ориентированном графе (алгоритм Флойда)

3 Поиск каркаса минимального веса в графе (алгоритм Краскала)

4 Задача Минисеть Проектируется оптимальная сеть дорог, которые должны связать несколько населенных пунктов так, что из любого пункта можно проехать в любой другой. Каждая дорога представляет собой отрезок, соединяющий какие-то два пункта. Суммарная длина всех дорог должна быть минимальна. Программа должна: обеспечить ввод числа пунктов; обеспечить ввод координат каждого пункта; спроектировать сеть дорог, и найти их суммарную длину; вывести результаты. Пример : Число пунктов : 7 Координаты пунктов : 0, 0 0, 3 3, 0 3, 3 3, 5 4, 4 5, 3 Ответ Соединим дорогами пункты : Общая длина дорог 13.24

5 Общая постановка задачи В связанном неориентированном графе, описанном перечислением ребер, найти каркас наименьшего суммарного веса. Число вершин – 5 Число ребер – 7 D[1..k,1..3] Дорога Начало Конец Длина

6 Первый шаг Сортируем ребра по длине Ребро Начало Конец Длина i:=1; While (iD[i+1,3]) then For j:=1 to 3 do Begin r:=D[i,j]; D[i,j]:=D[i+1,j]; D[i+1,j]:=r; if (i>1) then i:=i+1 else i:=2; End else i:=i=1;

7 Второй шаг Заполняем таблицу флагов F[1..k] Вершина Флаг For j:=1 to k do F[i]:=i;

8 Третий шаг Основная часть логики Вершина Флаг S:=0; p:=0; Writeln(Ребра); While (p

9 Поиск кратчайшего пути в ориентированном графе (алгоритм Флойда)

10 Задача Квадратная таблица t(n,n) содержит стоимости авиационного перелета между городами. Заполните таблицу st(n,n) наименьших стоимостей перелетов между городами, включающую варианты перелета с пересадками.

11 Общая постановка задачи Для ориентированного графа с матрицей весов A[1..n,1..n] (целые числа) заполнить матрицу кратчайших расстояний между всеми парами вершин графа и кратчайшие пути Число вершин – n Число ребер – k Матрица смежности вершин – A[1..n,1..n] Вершина

12 Заполнение вспомогательных матриц Введем две матрицы D[1..n,1..n] для хранения оценок кратчайшего пути из i в j с промежуточными вершинами кратчайшего пути. А также матрицу M[1..n,1..n] в которой будем хранить номер предпоследней вершины кратчайшего маршрута. D For i:=1 to n do For j:=1 to n do Begin D[i,j]:=A[i,j]; M[i,j]:=i; End; M

13 Обработка матриц D, M с использованием матрицы A D For m:=1 to n do For i:=1 to n do For j:=1 to n do if (D[i,j]>=D[i,m]+A[m,j]) then begin D[i,j]:=D[i,m]+A[m,j]; M[i,j]:=M[m,j]; end; M

14 Результаты обработка матриц D, M с использованием матрицы A D M

15 Поиск кратчайшего пути D M Поиск кратчайшего пути из 3 в 1 Длина кратчайшего пути из 3 в 2 равна 4 (таблица D) Маршрут В 3 из 1 (M[3,2]=1) В 1 из 4 (M[3,1]=4) В 4 из 3 (M[3,4]=3) Кратчайший путь из 3 в 2 составлен 3 – 4 – 1 – 2

16 И это еще не все, но... КОНЕЦКОНЕЦ