Общая идея алгоритма состоит в следующем: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них
1. Выбираем любую вершину из еще не пройденных, обозначим ее как u.
2. Запускаем процедуру dfs(u)
• Помечаем вершину u как пройденную
• Для каждой не пройденной смежной с u вершиной (назовем ее v) запускаем dfs(v)
3. Повторяем шаги 1 и 2, пока все вершины не окажутся пройденными
DFS применяется в:
- Топологической сортировке.
- Поиска точек сочленения, мостов.
- Поиска циклов
Время: O(n + m)
Память: O(n)
потом тут будет реализация
void DFS(int v) {}
1. Помечаем все вершины как не пройденные
2. Добавляем в очередь стартовую вершину
3. В цикле: (пока очередь не пустая)
a. Берем вершину из очереди и помечаем ее как пройдённую
b. Добавляем в очередь все смежные с ней вершины, которые не пройденные
c. Удаляем из очереди пройденную вершину
BFS применяется в:
- Поиске компонент связности в графе
- Поиске кратчайшего пути между двумя узлами невзвешенного графа
- Нахождении кратчайшего цикла в ориентированном невзвешенном графе
Время: O(n + m)
Память: O(n)
- Только для ациклических ориентированных графов!
- Сортирует граф, таким образом, что для любой дуги (u, v) u будет перед v
- По сути просто DFS, где мы каждую посещенную вершину добавляем в стэк
1. Выбираем любую вершину из еще не пройденных, обозначим ее как u.
2. Запускаем процедуру dfs(u)
• Помечаем вершину u как пройденную
• Для каждой не пройденной смежной с u вершиной (назовем ее v) запускаем dfs(v)
3. Каждую пройденную (черную) вершину помещаем в стек
4. Повторяем шаги 1-3 пока все вершины не окажутся пройденными
Время: O(n + m)
Память: O(n)
Компоненты сильной связности в орграфе G можно найти с помощью поиска в глубину в 3 этапа:
1. Запустить топсорт (DFS по ИСХОДЯЩИМ РЁБРАМ). В графе могут быть циклы, поэтому граф не совсем отсортируется, но это нужно для
гарантии того, что вершины одной компоненты будут левее вершин другой. Добавить все отсортированные вершины в массив/стек.
2. Создать массив компонент components размера n и счётчик компонент counter.
3. Для каждой вершины в отсортированном массиве/стеке:
• Если ещё не найдена её компонента, то запускаем DFS по ВХОДЯЩИМ РЁБРАМ и всему, что он обойдет присваиваем значение счетчика
• Инеркментируем счетчик
4. В реузльтате получим, что components[i] - это номер компоненты, которой принадлежит i-я вершина.
void outDFS(u): // по ИСХОДЯЩИМ
graph[u].color = 1
for v in graph[u].out:
if graph[v].color == 1:
outDFS(v)
stack.push(u)
void inDFS(u): // по ВХОДЯЩИМ
components[u] = counter
for v : graph[u].in:
if components[v] == 0:
inDFS(v)
// после запуска outDFS (топсорта)
int condense(graph):
counter = 1
for u in stack:
if components[u] == 0:
counter++
inDFS(u)
return counter // возвращает количество компонент сильной связности
// если хочется, можно объединить все вершины для каждой из компонент в отдельные списки
Время: O(n + m)
Память: O(2n)
• Обходим граф. Каждую вершину, в которой мы не были, кладем в стэк и запускаем DFS из неё.
• Если DFS пытается пойти в серую вершины - цикл найден.
• Когда DFS нашел вершину, которая лежит на цикле (Un), последовательно вынимаем все вершины из стэка (U1...Un-1, пока не
встретим найденную (Un) еще раз.
• Все вынутые из стека вершины будут являться циклом.
• Тут тоже самое, но мы должно проверять, что для рассатриваемой нами вершины ребро UV не является ребром, по которому
мы пришли в эту вершину
Время: O(n + m)
Для не орграфа.
Критерий эйлеровости (существует эйлеров цикл):
1. Все вершины имели четную степень.
2. Все компоненты связности кроме, может быть одной, не содержали ребер.
Критерий полу-эйлеровости (существует эйлеров путь):
1. Количество вершин с нечетной степенью меньше или равно (?) двум.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Для орграфа.
Критерий эйлеровости (существует эйлеров цикл):
1. Входная степень любой вершины равна ее выходной степени.
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
Критерий полу-эйлеровости (существует эйлеров путь):
1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа:
• для одной из которых deg(+) − deg(−) = 1
• а для другой deg(+) − deg(−) = −1
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
1. Проверяем критерии и заодно находим стартовую вершину с нечетной степенью (если будет 2 нечетных).
2. Кладём в стек стартовую вершину.
3. Запускаем модифицированный DFS:
• Смотрим на верхнюю вершину u стека (пока не удаляем её)
• Проходим по смежным вершинам (for v in u.смежные)
• Если ребро uv не помечено, помечаем, пушим v в стеку и запускаем DFS
• После того как прошлись по всем смежным, выводим u и удаляем её из стека
// после проверки критериев запускаем DFS от стартовой вершины
// matrix - матрица смежности
void DFS():
if stack.empty():
return;
int u = stack.top();
for v in u.neighbours:
if (matrix[u][v] == 0):
matrix[u][v] = 1;
matrix[v][u] = 1; // для не орграфа надо помечать и симметричное относительно главной диагонали матрицы
stack.push(v);
DFS();
print(v);
stack.pop();
1. Помечаем все вершины как не пройденные
2. Цикл пока есть не пройденные вершины
• Запускаем обход в глубину от вершины
• Все пройденные вершины собираем в первую компоненту
• Ищем не пройденную вершину
3. Выводим все компоненты графа
void DFS(u):
u.mark = true
components[u] = counter
for v in u.neighbours:
if (v.mark == false):
DFS(v)
counter = 0
for u in graph:
if u.mark == false:
counter++
DFS(u)
Время: O(n + m)
Память: O(n)
Для реализации потребуется Система Непересекающихся Множеств (СНМ), у которой есть 2 основные функции:
• get(v) - получить представителя вершины v (представителя множества, в котором находится v)
• union(u, v) - объединить множества, в которых находятся вершины u и v.
Алгоритм:
1. В начале у нас n множеств: каждое состоит из одной вершины, которая является представителем.
2. Отсортируем ребра по неубыванию по их весам.
3. Запускаем for для каждого ребра uv из отсортированного массива ребер:
• Если вершины u и v этого ребра в разных множествах, то объединяем их множества и прибавляем вес uv в ответ.
sort(edges)
for uv in edges:
if get(u) != get(v):
result += uv.weight
union(u, v)
Время: O(mlogm) Память: O(n)
1. Инициализируем MST с произвольно выбранной вершины.
2. Добавляем все смежные ребра и вершины при них в очередь с приоритетом (вершина с минимальным ребром будет первым элементов в куче)
3. Берем вершину до которой минимальный вес и добавляем ее в MST.
4. Повторяем шаг 3, пока не получим MST.
Время: (куча) O(n log m)
Динамика. Время О(nm).
Если на повторной (k == n)-й итерации найдётся такой v, что dist[n][v] < dist[n - 1][v],
то в графе есть отрицательные циклы.
- втупую:
dist = [k][n] // матрица k на n заполненная бесконечностями
dist[0][start] = 0
for k in range(1, n):
for v in range(n):
for uv in Edges[v]:
dist[k][v] = min(dist[k - 1][v], dist[k - 1][u] + uv.weight)
- экономим память:
dist = [inf for i in range(n)]
dist[start] = 0
for k in range(n):
for uv in Edges:
dist[v] = min(dist[v], dist[u] + uv.weight)
- по-хитрому:
dist = [inf for i in range(n)]
dist[start] = 0
while (!ok):
ok = true
for v in Vertices:
for uv in Edges[v]:
if dist[u] + uv.weight < dist[v]:
dist[v] = dist[u] + uv.weight
ok = false
Время: O(n * m) Память: или O(n^2) или O(n)
Вариант 1) Динамика вперёд:
1. Запускаем топсорт. Получаем вершины в топологическом порядке.
2. Заводим массив расстояний dist такой, что:
• до start (стартовой вершины) dist(start) = 0
• для остальных dist(i) = inf
3. Запускаеи динамику: dist(i) = min(dist(j) + w(j, i)), где j - вершина-предок для i.
Почему нам важно смотреть вершины в порядке топ. сорта?
При проходе по графу мы всегда знаем, что для более маленькой задачи
(для вершин расположенных ранее в топсорте) результат уже вычислен.
Вариант 2) Динамика назад:
1. Заведём массив расстояний до детей.
2. Запустим BFS.
3. Для каждой вершины будем обновлять расстояние до сына в том случае,
если хотя бы для одного потомка в таком случае уменьшится расстояние.
Как Прим, только данные о метках используются для поиска расстояний.
Поиск кратчайших путей от каждой вершины до каждой для любого веса рёбер. Время работы О(n^3).
Если после какой-то итерации на главной диагонали появились числа < 0, то в графе есть
отрицательные циклы. Нужно выводить его и брейкать на этом моменте, чтобы избежать переполнения.
// заполняем матрицу расстояний n x n
dist[n][n]
for i in range(n):
for j in range(n):
if (i == j):
dist[i][j] = 0
else:
dist[i][j] = weight(i, j)
for k in range(n):
for i in range(n):
for j in range(n):
// если есть промежуточная вершина k, то путь от i до j = путь от i до k + путь от k до j
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])