Skip to content

Latest commit

 

History

History
207 lines (162 loc) · 13.6 KB

mst.md

File metadata and controls

207 lines (162 loc) · 13.6 KB
Raw

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

Рассмотрим задачу нахождения минимального остовного дерева во взвешенном связном неориентированном графе. Минимальным остовным деревом называется такое подмножество ребер графа наименьшего суммарного веса, что образованный этим множеством подграф на вершинах исходного графа является деревом. Как и любое другое дерево на n вершинах, минимальное остовное дерево содержит ровно n - 1 ребер.

Жадное решение

Итак, нам нужно найти остовное дерево наименьшего веса. Тогда давайте отсортируем все ребра по возрастанию весов и возьмем первые n - 1, в итоге вы точно получим множество ребер наименьшего веса. Пусть граф задан списком ребер вида (v, c(v, u), u).

mst = []

def finished():
    return len(mst) == n - 1

def add_edge(edge):
    mst.append(edge)

def cost(edge):
    return edge[1]

def build_mst():
    edges = sorted(edges, key=cost)
    
    next_edge = 0
    while not finished():
        add_edge(edges[next_edge])
        next_edge += 1

Но будет ли это деревом? Необязательно, так как выбранные ребра могут образовывать циклы. Тогда будем добавлять ребро, только если оно не образует цикл.

def adds_cycle(edge):
    pass

def build_mst():
    edges = sorted(edges, key=cost)
    
    next_edge = 0
    while not finished():
        edge = edges[next_edge]    # <-- здесь добавили
        if not adds_cycle(edge):   # <-- проверку на
            add_edge(edge)         # <-- образование цикла
        next_edge += 1

Осталось только придумать, как мы будем определять образование цикла. Если при добавлении ребра (v, c(v, u), u) образуется цикл, значит, вершины v и u уже были соединены некоторой цепью. Поэтому добавлять ребро нужно, только если вершины v и u принадлежали разным компонентам связности, при этом, при добавлении ребра эти компоненты связности нужно объединять в одну. Выходит, нам нужно две операции: определение компоненты связности и объединение двух компонент связности. Таким интерфейсом обладает система непересекающихся множеств. Добавим ее:

components = dsu(n)

def add_edge(edge):
    v, _, u = edge
    components.union(v, u)
    mst.append(edge)

def adds_cycle(edge):
    v, _, u = edge
    cv = components.find(v)
    cu = components.find(u)
    return cv == cu

Если граф несвязный, то мы не сможем построить связное дерево и условие в while никогда не будет выполнено. Поэтому, чтобы предотвратить возможные ошибки, добавим проверку на число проверенных ребер:

def build_mst():
    edges = sorted(edges, key=cost)
    
    next_edge = 0
    while not finished() and next_edge < m: # <-- здесь!
        edge = edges[next_edge]
        if not adds_cycle(edge):
            add_edge(edge)
        next_edge += 1

Рассмотрим подробнее случай несвязного графа. В этом случае упорядоченный список ребер можно рассматривать как слияние упорядоченных списков ребер каждой компоненты. То есть списки ребер каждой компоненты также рассматриваются в порядке возрастания весов и добавляются к ответу, если объединяют две части одной компоненты связности исходного графа. Таким образом, при несвязном графе на выходе алгоритма мы получим множество минимальных остовных деревьев для каждой из компонент, что в совокупности образует минимальный остовный лес.

Соберем все вместе:

mst = []
components = dsu(n)

def finished():
    return len(mst) == n - 1

def add_edge(edge):
    v, _, u = edge
    components.union(v, u)
    mst.append(edge)

def adds_cycle(edge):
    v, _, u = edge
    cv = components.find(v)
    cu = components.find(u)
    return cv == cu

def cost(edge):
    return edge[1]

def build_mst():
    edges = sorted(edges, key=cost)
    
    next_edge = 0
    while not finished() and next_edge < m:
        edge = edges[next_edge]
        if not adds_cycle(edge):
            add_edge(edge)
        next_edge += 1

Сортировка выполняется за O(m log m), всего мы делаем O(m) запросов к СНМ, каждый из которых работает за почти константное время (O(alpha(n)), где alpha -- обратная функция Аккермана), поэтому общее время работы составляет O(m log m). Алгоритм называется алгоритмом Краскала.

Почему этот жадный алгоритм дает верное решение? Рассмотрим случай с уникальными весами ребер, так как в этом случае минимальное остовное дерево единственно. Докажем от противного. Пусть алгоритм построил дерево T, в то время как оптимальным деревом является T*, и T != T*. Тогда рассмотрим ребра графа в отсортированном по весу порядке, проверяя их принадлежность T и T*. Возьмем первое встреченное ребро e, по которому решения разошлись (то есть по всем ребрам e', c(e') < c(e), решения совпали). У нас имеется два случая:

  • e принадлежит T* и не принадлежит T. Так как мы рассматриваем ребра в порядке возрастания весов, то e не может принадлежать T только в случае, если оно образует цикл с ребрами, добавленными ранее. Но так как все ребра с весом < c(e) у T совпадают с T*, то и в T* ребро e тоже должно образовать цикл, что невозожно. Получаем противоречие.
  • e принадлежит T и не принадлежит T*. Рассмотрим вершины v и u, инцидентные e. В дереве T* эти вершины также должны быть соединены некоторой цепью, поэтому рассмотрим ребра этой цепи. У нас опять два случая:
    • Веса всех ребер этой цепи меньше c(e). В таком случае, как и выше, все эти ребра принадлежали бы и T, и добавление ребра e создало бы цикл, что по построению невозможно. Получили противоречие.
    • В цепи есть хотя бы одно ребро e', что c(e') > c(e). В таком случае в дереве T* мы можем заменить ребро e' на e и и получить новое дерево меньшего веса, чем T*. Получаем противоречие с утверждением, что T* -- оптимальное решение.

Доказательство можно расширить и для случая с неуникальными весами ребер.

Еще один жадный алгоритм

Рассмотрим какую-нибудь вершину v связного графа. Она точно должна принадлежать минимальному остовному дереву, причем ее степень в нем должна быть не менее 1. Значит, какое-то из инцидентных ей ребер будет принадлежать оптимальному решению. Тогда давайте выберем самое легкое инцидентое вершине v ребро и добавим его в дерево. Теперь в нашем дереве содержится две вершины и одно ребро. Рассмотрим опять все ребра, которые начинаются в нашем дереве и ведут в вершины, еще не принадлежащие дереву. Опять выберем среди них самое легкое и добавим его. Будем продолжать так делать, пока еще есть ребра, ведущие наружу.

Таким образом, мы постепенно расширяем строящееся дерево, имея на каждом шаге алгоритма минимальное остовное дерево на обработанном наборе вершин. Так как нам нужно выбирать каждый раз самое легкое ребро, то воспользуемся приоритетной очередью (больший приоритет имеет элемент с меньшим ключом). Чтобы добавлять в дерево только ребра, ведущие наружу, заведем массив in_mst, изначально заполненный False, который будет хранить, принадлежит ли вершина дереву или еще нет. В очередь же будем добавлять все исходящие из вершины ребра, чтобы упростить реализацию.

mst = []

def build_mst(start):
    q = PriorityQueue()
    
    in_mst[start] = True
    for u, cu in g[start]:
        q.enqueue((cu, start, u))
    
    while not q.empty():
        cu, v, u = q.dequeue()
        if in_mst[u]:
            continue
        
        in_mst[u] = True
        mst.append((v, cu, u))
        for w, cw in g[u]:
            q.enqueue((cw, u, w))

Так как мы заносим O(m) ребер в приоритетную очередь, то время работы алгоритма составляет O(m log m). При этом его можно ускорить до O(m log n), если хранить в очереди не ребра, а расстояния от уже построенного дерева до вершин, и изменять их нахождении меньшего значения. Алгоритм называется алгоритмом Прима.

В случае несвязного графа мы построим минимальное остовное дерево лишь одной компоненты связности (которой принадлежит стартовая вершина). Если мы хотим получить минимальный остовный лес, то алгоритм необходимо запускать для каждой вершины, не входящей в лес:

for v in range(n):
    if not in_mst[v]:
        build_mst(v)

Доказательство корректности этого алгоритма для графов с уникальными весами очень похоже на предыдущее доказательство. Найдем ребро e, первое добавленное алгоритмом, которое не содержится в оптимальном решении T*. Это значит, что инцидентные ему вершины соединены какой-то другой цепью в T*. Найдем в этой цепи такое ребро e', что одна инцидентная ему вершина уже принадлежит построенному дереву, а вторая -- еще нет. Так как наш алгоритм не выбрал ребро e' на данном шаге, то c(e') > c(e), а значит, мы можем заменить ребро e' на ребро e и получить остовное дерево меньшего веса, что приводит к противоречию об оптимальности T*. Доказательство можно обобщить и для случая с неуникальными весами ребер.