3. Алгоритмы

   1. Обход графа в глубину

Обойти граф — посетить каждую его вершину.

Алгоритм перебора с возвратом. Использует булевы метки «посещён/не посещён».

1. Выбирается начальная вершина графа. Помещаем в стек.

2. Извлекаем вершину, которая связана с первой. Помечаем пройденную вершину в TRUE. Если в вершину уже заходили, не рассматриваем.

3. Перебираем все значения.

4. Далее извлекаем вершины из стека.

5. Если у извлечённой есть непосещённые соседи, двигаемся вниз снова.

Пример:

1\ -2- /3

5\\ -\8/ 9

7- \6 \^4/

Стек: 7,6,5,4,3,2,1

6,5,4,3,2,1

8,5,4,3,2,1

5,4,3,2,1

4,3,2,1

9,4,3,2,1

4,3,2,1

3,2,1

2,1

1

Обход графа закончен.

Дерево обхода:

1 -2- /3

5\\ -8 9

7- \6 \^4/

Трудоёмкость: V+E.

2. Обход графа по уровням

(МП2)

Трудоёмкость: V+E.

3. Транзитивное замыкание

Транзитивность бинарного отношения R на множестве X означает, что если для любых трёх элементов A,B,C множества X выполнение отношения aRb и bRC → aRc .

Матрица связности — единицы в [i,j] означает, что из i-ой вершины существует путь в j-ю вершину длины 1, либо больше.

Транзитивное замыкание для матрицы смежности A обычно записывают как A+.

Можно найти умножением матрицы A самой на себя.

Сложность: O(n^3)

A → A^2 → A^4 → A^8 …

Сложность: O(n^3 * log(n,2))

sum(a_ik*b_kj)

for k = 1 to n do

for i = 1 to n do

for j = 1 to n do

A_k(i,j) = A_k-1(i,j) or [A_k-1(i,k) and A_k-1(k,j)]

(МП3)

4. Поиск сильносвязных компонентов в графе

Матрица достижимости (R) — элемент равен 1, если существует путь из i в j, иначе 0.

Матрица контрдостижимости (Q) — если из j в i есть путь, то 1, иначе 0.

Матрица взаимодостижимости (H) — если из i в j существует путь и из j в i существует путь, то 1.

Сильносвязные подграфы (компоненты) в графе.

1. алгоритмом поиска в ширину или глубину найти матрицу R.

2. Q = R^T

3. H. конъюнкция матриц R и Q.

(МП4)

5. Поиск кратчайших путей

Min G(1,S,k+1) = min(Min G(1,S,k), Min G(1,i,k) + a_i,s)

i = 1 … r .

i — все возможные пункты пересадки.

Алгоритм Форда-Беллманна.

Сложность: O(n^3).

Алгоритм Флойда:

A(i,j,0) = a_i,j ;

A(i,j,k+1) = a_i,j = min (A(i,j,k), A(i,k+1,k)+A(k+1,j,k)) ;

Алгоритм Дейкстры. Используется идея обхода в глубину. В процессе этого вычисляются стоимости (суммы весов) от начальной вершины до каждой из выбранных.

6. Минимальное остовное дерево

Остов графа включает все узлы, но не все рёбра.

Минимальный остов — сумма всех весов оставшихся рёбер минимальна.

Алгоритм Дейкстры-Прима («жадный» алгоритм)

Алгоритм, который выбирает наилучший вариант на данном шаге.

В качестве начального выбирается какой-то узел. Например, с номером один. Отыскивается обрамление этого узла. Обрамление - находящиеся на расстоянии 1 ребра от остова. В обрамлении в качестве следующего выбирается узел, расстояние которого от остова минимально. Узел, к которому идёт короткое ребро, добавляется в остов.

Сложность: O(2^n)

(МП5)

Алгоритм Кроскалла (поиска минимального остова)

Все рёбра сортируются в порядке возрастания весов. Остров строится с ребра минимального веса. Затем следующего и т.д.

Поиск компонент двусвязности.

Если удалить одну вершину со всеми связями, оставшиеся будут иметь связь.

Пример:

(МП6)

Сложность: O(n^2)