Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Граф – это набор вершин (узлов) и соединяющих их ребер (дуг).
Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления.
Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь).
Цикл – это цепь из какой-то вершины в нее саму.
Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина).
Связный граф – это граф, в котором существует цепь между каждой парой вершин.
k-cвязный граф – это граф, который можно разбить на k связных частей.
Полный граф – это граф, в котором проведены все возможные ребра (n вершин → n(n-1)/2 ребер).
Весовая матрица – это матрица, элемент W[i,j] которой равен весу ребра из вершины i в вершину j (если оно есть), или равен ∞, если такого ребра нет.
Задача Прима-Краскала
Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная.
Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа (остовное дерево) и имеющий наименьший вес.
Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент
Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению. В задаче Прима-Краскала жадный алгоритм дает оптимальное решение!
Реализация алгоритма Прима-Краскала
Проблема: как проверить, что
1) ребро не выбрано, и
2) ребро не образует цикла с выбранными ребрами.
Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра.
.gif)
Алгоритм:
покрасить все вершины в разные цвета;
сделать N-1 раз в цикле:
выбрать ребро (i,j) минимальной длины из всех ребер, соединяющих вершины разного цвета;
перекрасить все вершины, имеющие цвет j, в цвет i.
вывести найденные ребра.
Реализация алгоритма Прима-Краскала
Структура «ребро»:
type rebro = record
i, j: integer; { номера вершин }
end;
Основная программа:
const N = 5;
var W: array[1..N,1..N] of integer;//весовая матрица
Color: array[1..N] of integer;//цвета вершин
i, j, k, min, col_i, col_j: integer;
Reb: array[1..N-1] of rebro;
begin
... { здесь надо ввести матрицу W }
for i:=1 to N do { раскрасить в разные цвета }
Color[i] := i;
...{основной алгоритм – заполнение массива Reb}
... {вывести найденные ребра (массив Reb)}
end.
Основной алгоритм:
for k:=1 to N-1 do begin//нужно выбрать всего N-1 ребер
min := MaxInt;
for i:=1 to N do//цикл по всем парам вершин
for j:=i+1 to N do
if (Color[i] <> Color[j]) and //учитываем только пары с разным цветом вершин
(W[i,j] < min) then begin
min := W[i,j];
Reb[k].i := i;
Reb[k].j := j;
col_i := Color[i];//запоминаем ребро и цвета вершин
col_j := Color[j];
end;
for i:=1 to N do
if Color[i] = col_j then //перекрашиваем вершины цвета col_j
Color[i] := col_i;
end;
Сложность алгоритма
Основной цикл:
for k:=1 to N-1 do begin
...
for i:=1 to N do //три вложенных цикла, в каждом число шагов <=N
for j:=i+1 to N do
...
end;
Количество операций растет не быстрее, чем N^3
Требуемая память :
var W: array[1..N,1..N] of integer;
Color: array[1..N] of integer; => O(N^2)
Reb: array[1..N-1] of rebro;
26.
