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

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

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

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

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

Первый шаг Сортируем ребра по длине Ребро Начало Конец Длина i:=1; While (i<k) do if (D[i,3]>D[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;

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

Третий шаг Основная часть логики Вершина Флаг S:=0; p:=0; Writeln(Ребра); While (p<n-1) do Begin i:=1; while (F[D[1,i]]=F[D[[2,i]]) do i:=i+1; p:=p+1; S:=S+D[3,i]; writeln(D[1,i], –,D[2,i]); X:=F[D[1,i]]; for j:=1 to k do if (F[D[2,j]=X) then F[D[2,j]]:=F[D[1,j]]; End; Writeln(Суммарная длина,S) Ребро Начало Конец Длина

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

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

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

Заполнение вспомогательных матриц Введем две матрицы 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

Обработка матриц 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

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

Поиск кратчайшего пути 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

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