Лекции - Структуры и алгоритмы компьютерной обработки данных / 16.Алгоритмы на графах. Графы и различные способы их представления. Поиск в глубину

Алгоритмы на графах

Графы – удобная модель объектов, структур, явлений и процессов.

Основные понятия: неориентированный граф, ориентированный граф, мультиграф, вершины, ребра, дуги, смежность, инцидентность, степень, полустепень исхода, полустепень захода, связность, маршрут, путь, цикл, взвешенный граф (сеть), подграф,.

Частные виды графов: дерево, лес, полный граф, двудольный граф, ациклический граф.

Классификация графов по насыщенности

Пусть |V|=n, |E|=m.

Граф называется насыщенным (плотным), если m = Ө(n2). Граф называется ненасыщенным (разреженным), если m = Ө(n).

Насыщенность графа определяет, какой алгоритм будет более эффективным. Например для построения минимального остовного дерева разработаны алгоритм Прима-Дейкстры (Ө(n2)) и алгоритм Краскала-Борувки (Ө(mlogm)).

Если n=1000, то сложность первого алгоритма всегда 1 млн. Для насыщенного графа сложность второго алгоритма– 20 млн, для разреженного – 10 тысяч.

Представления графа в памяти компьютера

• Матрица смежности

• Списки смежных вершин

• Списки ребер

Матрица смежности

0	0	1	1	0	0	0	0
1	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0
0	1	0	0	1	0	0	0
0	1	0	0	0	0	0	0
0	0	0	0	1	0	1	0
0	0	0	0	0	0	0	1
0	0	0	0	1	0	0	0

Сложность операций

Объем памяти - Ө(n2)

Добавить ребро - Ө(1)

Найти ребро - Ө(1)

Удалить ребро - Ө(1)

Список вершин, смежных с данной Ө(n)

Списки смежных вершин

1	→	3	4
2	→	1
3	→	4
4	→	2	5
5	→	2
6	→	5	7
7	→	8
8	→	5

Различные способы хранения списков смежности

• Массив указателей на списки

• Динамический двумерный массив

• Одномерный массив смежных вершин + массив номеров первых соседей

Сложность операций

Объем памяти - Ө(n + m)

Добавить ребро - Ө(1)

Найти ребро - Ө(n)

Удалить ребро - Ө(n)

Список вершин, смежных с данной Ө(n)

Упорядоченные списки ребер

1	1	2	3	4	4	5	6	6	7	8
3	4	1	4	2	5	2	5	7	8	5

Сложность операций

Объем памяти - Ө(m)

Добавить ребро - Ө(m)

Найти ребро - Ө(log m)

Удалить ребро - Ө(m)

Список вершин, смежных с данной Ө(log m + n)

Поиск на графе

Поиск на графе – перебор вершин графа, при котором переход от одной вершины к другой происходит по ребрам.

• Поиск в глубину – реализация перебора с возвратами

• Поиск в ширину – перебор в порядке возрастания расстояния от начальной вершины

Поиск в глубину

Для каждой вершины идем в смежную, ранее не рассмотренную. Если таких нет – возвращаемся в предыдущую вершину

procedure dfs(v: integer);

var k: integer;

begin

inc(NumPre); pre[v]:=NumPre;

for k:=1 to N do

if (A[v,k] > 0) and (pre[k]=0) then

begin P[k]:=v; dfs(k); end;

inc(NumPost); post[v]:=NumPost;

end;

Вызов из основной программы

for i:=1 to N do pre[i]:=0;

for i:=1 to N do

if pre[i]=0 then dfs(i);

Задачи, сводящиеся к поиску в глубину в неориентирован-ном графе

• Обнаружение циклов

• Поиск пути между вершинами

• Определение компонент связности

• Остовной лес

• Раскраска графа в два цвета (определение, является ли граф двудольным, поиск цикла нечетной длины)

• Поиск мостов и точек сочленения

Классификация ребер при поиске в глубину в орграфе

if pre[k]=0

then

• Древесные

else

if post[k]=0

• Обратные (цикл)

else

If pre[k]>pre[v]

• Прямые

else

• Поперечные

Топологическая сортировка ациклического орграфа

Перенумеровать вершины орграфа так чтобы каждое ребро вело из вершины с меньшим номером в вершину с большим номером.

Задача возникает при составлении планов и расписаний. Два решения:

• Поиск в глубину. Массив номеров post дает топологическую сортировку в обратном порядке.

• Очередь истоков (вершин, куда не входят ребра)