Алгоритм Крускала (также алгоритм Краскала) - алгоритм, который преобразовывает связный неориентированный граф в минимальное остовное дерево. На самом деле пока что непонятно, что делает он, поэтому разберём поподробнее.
Итак, у нас есть связный граф, который хранится в виде списков рёбер (позже это будет важно). Предположим, у нас есть задание: нам нужно связать все вершины так, чтобы общий их вес будет минимальным. Если говорить более по-умному, нам нужно получить из графа именно это самое минимальное остовное дерево.
Реализация
Сортировка рёбер (именно здесь нам и нужны списки)
Для каждого ребра в отсортированном списке смотрим, чтобы не образовывалось циклов, если его добавить. Если это так, то его можно добавить.
Продолжаем, пока не пройдём все рёбра.
Итак, сложность базового алгоритма: O(m^2 log m + n log m), где m - кол-во рёбер. Нужно отсортировать рёбра (это делается за O(m log m), а затем каждый раз проходить по рёбрам DFS’ом, для того, чтобы найти цикл. Это тратит ещё O(m+n) времени.
Улучшение алгоритма
Алгоритм работает ужасно медленно, поэтому его нужно улучшать. К сожалению, с сортировкой ничего нельзя сделать, однако можно свести проверку на то, принадлежат ли вершины одной компоненте связности, можно свести к О(1). Для этого нужно воспользоваться особой структурой под названием DSU.
DSU - disjoint set union, или по-русски система непересекающихся множеств, которая хранит ближайшего предка вершины. Структура имеет в себе две функции: нахождение родителя и объединение двух непересекающихся множеств в одно.
Родителя находим за O(1), ведь можно просто хранить массив с родителями в структуре. Пока каждая вершина не соединена с другими, то она является сама себе родителем. Но как только между какими-либо вершинами возникает ребро, то одна вершина становится родителем другой.
class DSU: def __init__(self, n): self.parent = list(range(n)) #каждая вершина имеет ближайшего родителя def find(self, i): if self.parent[i] == i: return i self.parent[i] = self.find(self.parent[i]) return self.parent[i] def union(self, i, j): root_i = self.find(i) root_j = self.find(j) if root_i != root_j: self.parent[root_i] = root_j return True return False
Нам больше не нужно проверять это DFS’ом, поскольку если мы знаем, что все вершины восходят к одной вершине, то они уже автоматически относятся к одной компоненте связности, и следовательно, если мы проведём ребро между ними, то у нас больше не будет дерева.
На самом деле этот алгоритм можно применять для разных случаев, и один из них - генерация стеночных алгоритмов. В мире есть два типа лабиринтов: клеточный и стеночный. По сути они мало чем различаются, но главное различие между ними - это то, как выглядят стенки в лабиринте. Места, где можно ходить - пустые клетки, они не различаются внутри алгоритма. Однако в клеточном лабиринте стена - присутствие ребра, а в стеночном - заполненная клетка, которая говорит, что между двумя клетками нельзя пойти.
Построение лабиринта
Поскольку мы хотим создать хороший лабиринт, нам нужно понять, каковы критерии хорошего лабиринта. Во-первых, он должен занимать максимальное кол-во территории. Во-вторых, в любом квадрате 2х2 клетки одного типа должны соотноситься с клетками другого типа как 1:3. Это добавит "правильности" лабиринту, а также будет визуально выглядеть лучше и можно гарантировать, что алгоритм Крускала работает корректно.
Для начала нужно проанализировать и создать "кишки" лабиринта, то есть всё, что внутри. Внутри как раз и должно содержаться визуализированное минимальное остовное дерево. А для того, чтобы построить его, нужно определиться, что со 100% вероятностью пойдёт в лабиринт (т.е. будет вершинами нашего графа). Самое логичное - взять клетки, у которых обе координаты - чётные и "прорубать" между ними проходы. Остаётся только для нашего удобства завести словарь, в котором будем хранить номер вершины и их координату (ибо сразу с координатами не очень удобно работать).
import random row, col = map(int, input().split()) r, c = row - (not row % 2), col - (not col % 2) maze = [[1 for i in range(c)] for j in range(r)] center = {} cnt = 0 for _r in range(0, r, 2): for _c in range(0, c, 2): maze[_r][_c] = 0 center[(_r, _c)] = cnt cnt += 1
Дальше нужно определиться, как сделать два лабиринта с одинаковым размером непохожими друг на друга, поскольку по идее все возможные рёбра создаются перебором. После того, как создали список, можно просто перемешать элементы в списке функцией random.shuffle(), а затем идти циклом for по элементам нового списка рёбер. Так мы добавим разнообразие в финальный вид лабиринтов.
dsu = DSU(cnt) vu = [] for _r in range(0, r, 2): for _c in range(0, c, 2): if _c + 2 < c: vu.append((center[(_r, _c)], center[(_r, _c+2)], (_r, _c+1))) if _r + 2 < r: vu.append((center[(_r, _c)], center[(_r+2, _c)], (_r+1, _c))) random.shuffle(vu)
Для каждого ребра теперь нужно проверить, принадлежат ли его вершины одной компоненте связности. Если да, то пропускаем (мы не хотим, чтобы наше дерево перестало быть деревом, топим за экологию так сказать). Если нет, то добавляем его в специальный массив с рёбрами лабиринта.
Теперь нужно сформировать сам лабиринт. Пусть стена обозначается 1, а проход - точкой. Нужно сначала поместить все вершины в матрицу (это можно сделать генератором). После из списка рёбер лабиринта нужно пройтись по каждому ребру. Чтобы найти проход между двумя его концами, нужно найти среднее арифметическое координат концов и заменить 1 на 0
for idx1, idx2, (wr, wc) in vu: if dsu.union(idx1, idx2): maze[wr][wc] = 0
Хотя лабиринт готов, всё ещё остаются места, где его можно улучшить. По факту, мы умеем хорошо генерировать только лабиринты, где кол-во столбцов и строк оба нечётные. Что ж, нужно адаптировать алгоритм и для чётного кол-ва строк или столбцов. К счастью (или к сожалению), для этого уже не обязательно использовать алгоритм Крускала. Для этого достаточно пройтись по последнему столбцу или строке и заменить первый, третий, пятый.... 2n-1 элемент на проход. Так мы обеспечим максимальное покрытие (получится так называемая бахрома для лабиринта). Лабиринт готов. Осталось обернуть его рамкой и где-нибудь открыть вход с выходом, чтобы люди (или другие алгоритмы) могли посещать его.
if row % 2 == 0: maze.append([1] * c) for j in range(0, c, 2): if maze[r-1][j] == 0: maze[r][j] = 0 if col % 2 == 0: for row_maze in maze: row_maze.append(1) for i in range(0, r, 2): if maze[i][c-1] == 0: maze[i][c] = 0
Другие применения
А где ещё можно использовать алгоритм Крускала? Да практически везде, где нужно соединить несколько объектов с минимальными затратами. Например, при постройке железных дорог: нужно соединить все города между собой, использовав минимальную длину дорог. Из неочевидного, создание минимального остовного дерева можно использовать в проектировании микросхем. Нужно соединить все контакты, при этом минимизируя длину проводников и избегая циклов.
Полная реализация алгоритма
import random row, col = map(int, input().split()) r, c = row - (not row % 2), col - (not col % 2) maze = [[1 for i in range(c)] for j in range(r)] center = {} cnt = 0 for _r in range(0, r, 2): for _c in range(0, c, 2): maze[_r][_c] = 0 center[(_r, _c)] = cnt cnt += 1 class DSU: def __init__(self, n): self.parent = list(range(n)) def find(self, i): if self.parent[i] == i: return i self.parent[i] = self.find(self.parent[i]) return self.parent[i] def union(self, i, j): root_i = self.find(i) root_j = self.find(j) if root_i != root_j: self.parent[root_i] = root_j return True return False dsu = DSU(cnt) vu = [] for _r in range(0, r, 2): for _c in range(0, c, 2): if _c + 2 < c: vu.append((center[(_r, _c)], center[(_r, _c+2)], (_r, _c+1))) if _r + 2 < r: vu.append((center[(_r, _c)], center[(_r+2, _c)], (_r+1, _c))) random.shuffle(vu) for idx1, idx2, (wr, wc) in vu: if dsu.union(idx1, idx2): maze[wr][wc] = 0 if row % 2 == 0: maze.append([1] * c) for j in range(0, c, 2): if maze[r-1][j] == 0: maze[r][j] = 0 if col % 2 == 0: for row_maze in maze: row_maze.append(1) for i in range(0, r, 2): if maze[i][c-1] == 0: maze[i][c] = 0 for i in maze: print(*i, sep='')
Авторы: Забнин Платон, Нагманов Данияр
