Leetcode detailed graph
Leetcode Detailed Graph
Source:: https://leetcode.com/explore/learn/card/graph/
Граф - нелинейная структура данных из вершин и ребёр. Между собой выделяют графы по следующим параметрам:
- направленные и ненаправленные
- цикличные и ацикличные
- с весами на рёбрах и без
Disjoint set
Disjoint set - структура данных для выделения независимых подграфов в графе. Для формирования disjoint set используются массивы, где индексом является вершина, а значение - корень в disjoint set. Корнем называем такое значение в массиве, где индекс == значению. Основными методами для данной структуры являются:
- find - найти корень текущего элемента
- union - объединить два элемента в одно множество
- connected - проверить что два элемента относятся к одному множеству
Довольно просто сделать операцию find - O(1), храня в массиве всегда ссылку только на корень, но это замедляет union до O(N). Ускорить union сложнее, потому что необходимо находить корень для обеих элементов.
Чтобы ускорить union мы должны балансировать входящее дерево. Для этого потребуется увеличить требования по памяти на ещё один массив. При соединение дерева мы выбираем дерево с большей высотой и присоединяем к нему новый массив.
Чтобы ускорить root, мы применяем рекурсию. При каждом поиске элемента мы устанавливаем ссылку на корень вместо элементы, с которым мы сцепляли. Таким образом худшее выполнение все ещё O(N), но все повторные операции будут близки к O(1).
Структуру UnionFind можно использоваться для поиска minimal spanning tree в рамках взвешеного направленного графа. Для этого мы создаём граф и проверяем соединены ли уже ноды в сет, если нет, то мы добавляем путь с минимальным весом и тем самым получаем требуемое дерево. (см. Kruskal’s algorithm)
Depth first path
Поиск пути в глубину используется для:
- поиска всех вершин в графе
- поиска всех путей между двумя вершинами в графе (сложность (V-1)! )
Делается с помощью стека (LIFO) или рекурсии. Общая идея в том, чтобы проверить все пути до последнего не посещённого элемента прежде, чем переходить к другому ближайшему соседу.
Bread first path
Всё тоже самое, что и DFS, только в этом случае мы проверяем сначала всех ближайших соседей. Для этого вместо стека (LIFO) используется очередь (FIFO).
Как правило, есть два варианта реализации. Наивная:
from collections import deque
queue = deque([start])
visited = set()
while queue:
elem = queue.popleft()
if elem in visited:
continue
visited.add(elem)
for n in elem.neighbours:
queue.append(n)
И по уровням:
from collections import deque
queue = deque([start])
visited = set()
level = 0
while queue:
size = queue.size()
for _ in range(size):
elem = queue.popleft()
if elem in visited:
continue
for n in elem.neighbours:
queue.append(n)
visited.add(elem)
level += 1
Minimal spanning tree
Spanning tree - подграф в ненаправленном графе, который соединяет все вершины минимальным количеством граней. Minimum spanning tree - в графе с весами соединяет с помощью минимального количества веса на гранях.
Для построения minimal spanning tree можно использоваться Kruskal’s алгоритм. Его метод заключается в том, чтобы добавлять рёбра в порядке возрастания весов, так чтобы не появлялись циклы. После того, как в графе окажется N-1 ребёр, где N - количество вершин. Kruskal’s алгоритм является частным случаем жадного алгоритма.
Shortest path
Короткий путь в графе без весов можно найти с помощью breadth first search. Когда же граф имеет веса на рёбрах, то есть более оптимальный решения для нахождения самого короткого пути:
- Dijkstra’s algorithm - для графа с положительными весами
- Bellman Ford - для графа с любыми весами
После попытки самостоятельной имплементации алгоритма Дийкстры в очередной раз забыл про существование heappq.
Bellman Ford алгоритм полагается на две Леммы:
- В любом графе без циклов или с положительным циклом самый короткий путь будет по длинне не больше, чем V-1.
- В любом графе с негативным циклом самого короткого пути нет, потому что мы можем бесконечно ходить по кругу.
Bellman Ford алгоритм оперирует матрицей Vx(E-1). На каждом этапе мы считаем минимальное расстояние между выбранным ребром + короткий путь с предыдущего шага и текущим коротким путём, который у нас есть. Поэтому в тупую bellman ford реаештся с помощью динамического программирования. Для его оптимизации вместо двумерного массива можно использовать два массива (предыдущий и текущий шаг) если нам важно количество использованных ребёр и одномерный массив с inplace расчётами.
Алгоритм SPFA использует алгорим Bellman Ford, но делает оптимизацию на выбираемые рёбра с помощью очереди выбора вершин.
Topological sorting
Kahn’s алгоритм - это алгоритм решения дерева зависимостей в направленном графе. Алгоритм берёт ноду с нулевым количеством входящих стрелок. После этого мы берём все у кого количество входящих стрелок за вычетом предыдущих нод = 0. И так далее. Для графа с циклом такой штуки, как topological sorting - нет.
Цитатник
- 202301161044: The Definition of “graph” and Terminologies
- 202301161147: Optimized UnionFind
- 202301191013: Find smallest string
- 202302051150: Primal’s algorithm