Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняНазвание 19 тем по алгоритмам и структурам данныхСтатья, давайте взглянем на минимальное остовное дерево.
Давайте не будем сначала говорить о принципе работы алгоритма, и мы не будем говорить о некоторых понятиях, потому что для новичков часто бывает головной болью увидеть эти термины и понятия. Также нормально иметь головную боль, потому что так много информации внезапно появляется без всякой причины, и я не знаю, откуда она взялась, и я не знаю, какая польза от этой информации, поэтому я, естественно, чувствую себя головная боль. Это также является причиной того, что многие люди с энтузиазмом относятся к изучению алгоритмов, но в конце концов их убеждают бросить это дело.
Давайте не будем говорить о том, что такое остовное дерево, как остовить дерево, ориентированные графы, неориентированные графы, давайте будем проще,Начните с основ, чтобы полностью разобраться в этом алгоритме.
что такое дерево
Для начала рассмотрим простейшую структуру данных — дерево.
Дерево — очень абстрактная структура данных, потому что оно может находить соответствующие объекты в природе. Когда мы впервые учимся, мы часто понимаем эту концепцию на основе реальных деревьев в природе. Итак, в нашем познании деревья часто растут вот так:
Вышеприведенная картинка представляет собой абстракцию деревьев в природе, которую нам легко понять. Но в целом древовидная структура, которую мы видим, часто не такая, ас ног на голову. То есть корни сверху, а листья снизу. Причина такого дизайна очень проста, особой причины нет, просто потому, что когда мы проходим по дереву, мы часто начинаем с корня дерева и начинаем от корня к конечному узлу. Так что это легко понять, когда мы переворачиваем его вверх ногами.Мы переворачиваем вышеприведенное дерево вверх ногами, и оно становится таким:
Вышеуказанные два способа рисования конечно правильны, но так как дерево можно расположить вверх ногами или вверх ногами, то мы, естественно, тоже можем разместить егопротянуть. Например, на картинке ниже на самом деле дерево, но мы рисуем его по-другому.
Мы можем себе представить, что если бы невидимая большая рука схватила корень дерева и «подняла его вверх», то оно естественным образом стало бы тем, что выше.
Тогда вы обнаружите, что если есть такая большая рука, какой бы узел она ни взяла, она получит дерево. То есть, если положение корня дерева нам уже не важно, дерево фактически эквивалентно графу выше.
Так что же это за картина? Какова его природа? Все ли графы можно рассматривать как деревья?
Очевидно, эти три случаяне дерево, во-первых, потому что ребра в графе имеют направления. С направлением связность в графе нарушается. В нашем восприятии дерево должно быть полноценным, как муравей в природе, который может перемещаться по дереву куда угодно.Если он не может быть полностью связан, это, конечно, не дерево.. Случай 2 также неверен, потому чтос кольцом, дерево не должно иметь циклов. Деревья в природе не имеют циклов, и нет ветви, которая сама по себе образует круг, Точно так же деревья в нашей логике не имеют циклов, иначе мы никогда не найдем конца рекурсивного доступа. То же верно и для третьего случая, когда некоторые точки изолированы,Не могу подключиться, а природа не дерево.
Итак, давайте подведем итоги и ответим на этот вопрос. Что такое дерево? Дерево — это полносвязный (неориентированный) граф, не имеющий циклов.
От графика к дереву
Только что проведя анализ, мы пришли к очень важному выводу,Суть дерева - это граф, это просто граф, который удовлетворяет некоторым специальным свойствам. Вот почему многие алгоритмы для деревьев включены в большую концепцию теории графов.
отПолностью подключен и без петельИсходя из этих двух свойств, мы можем сделать очень важный вывод: для дерева с n узлами количество его ребер фиксировано, а их должно быть n-1 ребер. Если ребер больше n-1, то должен быть цикл, а если меньше n-1 ребер, то должны быть несвязные части. Но обратите внимание, что это всего лишьнеобходимые условия, не является достаточным условием. Другими словами, нет необходимости, чтобы n точек и n-1 ребер были деревьями, для чего легко построить контрпримеры.
Этот вывод, хотя и простой, но очень полезный, он может решитьПреобразование графа в деревоПроблема.
То есть теперь у нас есть сложный граф, и мы хотим сгенерировать дерево, которое может соединить все узлы на основе этого графа, что нам делать в это время? Если у нас нет вышеперечисленных свойств, мы будем чувствовать себя немного беспомощными. Но с таким характером все становится намного понятнее. У нас есть два пути, первый путьобрезать край, так как это сложный граф, это означает, что количество ребер должно превышать n-1. Затем мы можем попытаться удалить некоторые ребра и получить дерево. Второй подход, напротив,добавить преимущество. То есть мы удаляем все ребра в начале, а затем добавляем n-1 ребер одно за другим, чтобы оно стало деревом.
Если мы попытаемся подумать об этом, мы обнаружим, что метод удаления ребер значительно слабее, чем добавление ребер. Причина проста, потому что каждый раз, когда мы удаляем ребро, мы сталкиваемся сРазрушит ли это отношения связи на деревепытка. Например, следующая картинка:
Если мы удалим ребро AB, то связность всей структуры будет разрушена. Для нас лучший способ оценить отношения связности — сначала удалить это ребро, а затем попытаться начать с точки А, чтобы посмотреть, сможем ли мы достичь точки Б. Если это так, ребро считается удаляемым. Если картинка большая,Каждое удаление требует обхода всего графа, что влечет за собой огромные накладные расходы. И каждое удаление меняет структуру графика, что затрудняет кеширование этих результатов.
Таким образом, метод удаления ребер не является неосуществимым, но его сложность очень высока, поэтому два самых популярных алгоритма минимального остовного дерева реализуются вторым методом, то есть добавлением ребер.
На данный момент мы знаем, что так называемый алгоритм минимального остовного дерева,Он состоит в том, чтобы выбрать n-1 ребер из графа и преобразовать его в дерево.алгоритм.
Решить проблемы со сборкой
Не будем рассматривать случай с весами на ребрах, будем считать, что все ребра эквивалентны, посмотрим, как сначала решить задачу генерации, а потом оптимизировать ее для минимизации.
Если мы используем метод добавления ребер, то проблемы, с которыми мы сталкиваемся, аналогичны вышеперечисленным: когда мы выбираем ребро, как мы судим, что это ребро необходимо добавить? Эта задача требует использования еще одного свойства деревьев.
Так как петель нет,Между любыми двумя точками дерева существует один и только один путь.. Потому что если есть два пути между двумя точками, то должна быть найдена петля. Его доказательство простое, но нам трудно прийти к такому выводу самостоятельно. Таким выводом можно ответить на поставленный выше вопрос, какое ребро необходимо добавить? То есть, когда нет пути между двумя точками. Если путь между двумя точками уже есть, текущее ребро добавить нельзя, иначе неизбежно появится кольцо. Если доступа нет, то его можно добавить.
Итак, что нам нужно сделать, так это разработать алгоритм, который можетСохранение связности точек на дереве.
Но это приносит новую проблему в древовидной структуре,Связность является транзитивной. Ребро соединено между двумя точками, причем соединены не только эти две точки, но соединены все точки, соединенные с этими двумя точками. Например, следующая картинка:
На этом рисунке А и В соединены ребром. Это не только то, что А и В соединены, но иВозможность подключения набора в левой половине и набора в правой половине. Таким образом, хотя А связано только с В, оно также связано с С. Ребро AC также не может быть добавлено. То есть, А и В связаны, на самом деле,Множество, в котором находится А, объединяется с множеством, в котором находится В.процесс. Вы чувствуете себя немного знакомым, когда видите слияние наборов? Правильно, алгоритм поиска объединения, о котором мы говорили в предыдущей статье, используется для решения проблемы слияния наборов и запросов. Тогда очевидно, что объединение множеств можно использовать для поддержания связности этих точечных множеств в графе.
Если вы забыли об алгоритме поиска союза, вы можете нажать на портал ниже, чтобы просмотреть:
Сорок строк кода, чтобы получить классический алгоритм объединения и поиска
Используя алгоритм поиска объединения, проблема очень проста. В начале все точки отключены, затемВсе точки сами по себе являются набором. Если две точки, соединенные текущим ребром, принадлежат одному множеству, это означает, что между ними уже есть путь, и это ребро нельзя добавить. В противном случае это означает, что они не связаны, тогда соедините ребро и объедините два множества.
Итак, мы решили задачу связующего дерева.
От остовного дерева к минимальному остовному дереву
Затем мы добавляем веса к каждому ребру в графе, надеясь, что результирующее дерево будет иметь наименьшую сумму всех весов.
Например, у нас есть следующая картинка, которую мы хотим сгенерироватьСумма весов всех ребер в дереве является наименьшей..
Посмотрите на края на этой картинке, длина разная. По жадному алгоритму мыОчевидно, нужно использовать кратчайшее возможное ребро для соединения дерева.. Поэтому принцип алгоритма Крускала очень прост и груб, то есть отсортировать эти ребра по длине, пройти эти ребра по очереди от коротких к длинным, а затем проверить, можно ли добавлять ребра, проверив множество до тех пор, пока не будут найдены все ребра. края пройдены.
Совершенно очевидно, что сгенерированное таким образом дерево должно быть правильным.Хотя мы отсортировали ребра, каждое ребро все еще можно использовать, и сортировка не повлияет на реализуемость алгоритма. Но вопрос в том, обязательно ли результат такой жадности оптимален?
Здесь мы все еще используем то, что сказали раньшеМетод оценки эквивалентности. Мы предполагаем, что есть два ребра одинаковой длины, так повлияет ли наше решение на конечный результат?
Для двух совершенно равных сторон возможны только три случая.Для упрощения иллюстрации мыДумайте о наборе как о точке. В первом случае эти два ребра соединяют четыре разных множества:
Тогда очевидно, что между этими двумя ребрами нет конфликта, поэтому мы можем оставить оба. Так что это не приводит к контрпримеру.
Второй случай состоит в том, что эти два ребра соединяют три разных множества:
Эта ситуация такая же, как и выше, она может быть у всех, и это не повлияет на подключение. Так что обратных примеров не будет.
Последнее состоит в том, что эти два ребра связаны с двумя множествами, то есть следующими.
В этом случае два условия противоречат друг другу, и мыТолько один из них может быть выбран. Но, очевидно, это то же самое, независимо от того, что мы выбираем. Поскольку эти два соединенных блока соединены, а затем значение одинаковое,не повлияет на конечный результат.
После того, как мы перечислим все ситуации, мы можем дать понять, что жадный метод реализуем в этой задаче и не вызовет контрпримеров, поэтому мы можем уверенно его использовать.
Практические проблемы и реализация кода
Поняв принцип алгоритма, давайте взглянем на реальную проблему этого алгоритма. На самом деле этот алгоритм довольно часто используется в реальности, например, водоканалу нужно соединить все населенные пункты водопроводом. И водопроводные трубы имеют свою стоимость, поэтому очевидно, что водопроводная компания хочетОбщая длина водопровода должна быть как можно короче.. Например, когда деревни в горах электрифицированы, все деревни должны быть связаны как можно меньшим количеством кабелей, на самом деле, эти похожие проблемы могут быть решены путем абстрагирования их в минимальное остовное дерево. Конечно, в действительности проблема может быть не такой простой.Помимо учета стоимости и связи, необходимо также учитывать многие другие факторы, такие как рельеф, гуманитарные и социальные факторы.
Наконец, попробуем реализовать этот алгоритм в коде.
class DisjointSet:
def __init__(self, element_num=None):
self._father = {}
self._rank = {}
# 初始化时每个元素单独成为一个集合
if element_num is not None:
for i in range(element_num):
self.add(i)
def add(self, x):
# 添加新集合
# 如果已经存在则跳过
if x in self._father:
return
self._father[x] = x
self._rank[x] = 0
def _query(self, x):
# 如果father[x] == x，说明x是树根
if self._father[x] == x:
return x
self._father[x] = self._query(self._father[x])
return self._father[x]
def merge(self, x, y):
if x not in self._father:
self.add(x)
if y not in self._father:
self.add(y)
# 查找到两个元素的树根
x = self._query(x)
y = self._query(y)
# 如果相等，说明属于同一个集合
if x == y:
return
# 否则将树深小的合并到树根大的上
if self._rank[x] < self._rank[y]:
self._father[x] = y
else:
self._father[y] = x
# 如果树深相等，合并之后树深+1
if self._rank[x] == self._rank[y]:
self._rank[x] += 1
# 判断是否属于同一个集合
def same(self, x, y):
return self._query(x) == self._query(y)
# 构造数据
edges = [[1, 2, 7], [2, 3, 8], [2, 4, 9], [1, 4, 5], [3, 5, 5], [2, 5, 7], [4, 5, 15], [4, 6, 6], [5, 6, 8], [6, 7, 11], [5, 7, 9]]
if __name__ == "__main__":
disjoinset = DisjointSet(8)
# 根据边长对边集排序
edges = sorted(edges, key=lambda x: x[2])
res = 0
for u, v, w in edges:
if disjoinset.same(u ,v):
continue
disjoinset.merge(u, v)
res += w
print(res)
На самом деле, основная цель — использовать и проверять набор, а дополнительный код, который мы написали, — это всего несколько строк.
конец
Я думаю, что всем также кажется, что принцип алгоритма Крускала очень прост, если вы читаете его по строкам статьи, я верю, что будет плавный поток, и все будет происходить естественным образом. Именно по этой причине оноочень интуитивно понятный,такжеочень легко понять, однажды вспомнив, нелегко забыть, и даже если мы забудем, мы можем легко вывести это самостоятельно. Это не шутка, я столкнулся с этим временно во время соревнований, я тогда давно не писал алгоритм Крускала и долго не мог его вспомнить. С небольшим впечатлением я просто вывел алгоритм на бумаге.
В следующей статье мы продолжим изучение задачи о минимальном остовном дереве и рассмотрим еще один похожий, но другой алгоритм — Prim.
Сегодняшняя статья здесь, оригинальность непростая, вам нужен вашбеспокойство, отсканируйте код, чтобы узнать о других интересных статьях.