26. Минимальное остовное дерево
Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty
Граф
Прежде чем перейти к описанию минимального остовного дерева, нужно пояснить некоторые моменты. Первое - граф. В нашем случае граф - это двумерный объект, состоящий из вершин (узлов) и рёбер. Где вершина (узел) - точка в графе, а ребро - пара вершин, соединённая линией. Далее разберём некоторые виды графов.
Взвешенный граф - это граф, рёбра которого имеют какое либо значение (вес), в нашем случае - числовое.
Неориентированный граф - это граф, в котором не указано направление рёбер. (1) Ориентированный граф - это граф, в котором указано направление рёбер. (2)
Связный граф - это граф, в котором между любой парой вершин существует хотя бы один путь. Путь - последовательность вершин, в которой каждая вершина соединена со следующей ребром. (1) Несвязный граф - это граф, в котором любые две вершины несмежны (никакая пара вершин не соединена ребром). (2)
Дерево и МОД
Второй момент - дерево. В нашем случае, дерево - это связный граф, в котором нет циклов. Также оно не является бинарным.
Остовное дерево - подграф графа, с тем же числом вершин, что и у исходного графа. (Остов - опорная/основная часть чего-либо)
Минимальное остовное дерево - это остовное дерево с минимальным общим весом во взвешенном связном графе.
Алгоритмы по поиску МОД
Алгоритм Краскала
Сначала берутся все рёбра графа и сортируются по возрастанию. Далее, пока не переберём все рёбра, производим следующие операции:
- Берём ребро из сортированного списка.
- Если добавление ребра не создаёт цикла, то добавляем его в дерево.
Схематическая работа алгоритма
Есть исходный граф.
Первый шаг
Берем наименьшее ребро, в нашем случаи это .
Второй шаг
Далее берем следующее по величине ребро.
Третий шаг
Выбираем ребро , так как оно наименьшее из оставшихся.
Четвёртый шаг
Выбираем следующее по величине ребро.
Пятый шаг
Выбираем следующее по величине ребро и проверяем создает оно цикл или нет.
Остальные ребра мы не можем взять, так как они создают цикл.
Вычислительная сложность
Сложность алгоритма: , где n - количество рёбер.
Псевдокод
Алгоритм Краскала рёбра <- сортированный список рёбер графа группы узлов <- СНП (Система непересекающихся подмножеств) для ребра в рёбрах если узел_1 и узел_2 из разных групп то добавляем ребро в дерево объединяем группы узлов вернуть дерево
Реализация на Python
Аннотация: tree_kraskal - алгоритм Краскала vertex - количества вершин в графе group_nodes - группы вершин edges - список ребер графа, отсортированных по весу edge - ребро графа
def tree_kraskal(self): vertex = len(self._adjacency_list) group_nodes = UnionFind(vertex) edges = sorted(self._edges_graph, key=Graph.__compare) for edge in edges: if not group_nodes.same_set(edge.from_node, edge.to): self._kraskal_tree.add_edge(edge) group_nodes.union_set(edge.from_node, edge.to) return self._kraskal_tree.edges_tree
Олимпиадная реализация на C++
Аннотация: typedef - переопределение имени типа данных kraskal - алгоритм Краскала edges - список ребер графа vtx - количество вершин в графе mst - вес минимального остовного дерева UF - группы вершин edge - ребро графа
typedef vector<int> vi; int kraskal(vector<vi> edges, int vtx) { int mst = 0; UnionFind UF(vtx); sort(edges.begin(), edges.end(), comp); for (vi edge : edges) { if (!UF.same_set(edge[0], edge[1])) { mst += edge[2]; UF.union_set(edge[0], edge[1]); } } return mst; }
Продуктовая реализация на C++
Аннотация: vector <Edge> Graph::tree_kraskal() - алгоритм Краскала vector <Edge> null_vector - Инициализация ребер vertex - количество вершин в графе group_nodes - группы вершин edges - список ребер графа edge - ребро графа
vector<Edge> Graph::tree_kraskal() { vector<Edge> null_vector; int vertex = count_nodes_graph; UnionFind group_nodes(vertex); vector<Edge> edges = list_edges_graph; sort(edges.begin(), edges.end(), compare); for (Edge edge : edges) { if (!group_nodes.same_set(edge.from, edge.to)) { kraskal_tree.append_edge(edge); group_nodes.union_set(edge.from, edge.to); } } return kraskal_tree.list_edges_tree; }
Алгоритм Прима
Берём произвольную вершину графа и находим минимальное ребро, которое с ней связано. Добавляем это ребро в дерево. Далее пока не переберём все рёбра графа, производим следующие операции:
- Из рёбер, которые связаны с деревом, выбираем минимальное.
- Если оно не создаёт цикла, добавляем ребро в дерево. В приведённом ниже примере начальная вершина -
Схематическая работа алгоритма
Есть исходный граф
Первый шаг
Выбираем произвольную вершину и выбираем ребро с наименьшей длиной
Второй шаг
Далее выбираем наименьшее ребро, исходящие из вершин и .
Третий шаг
Берем ребро, соединяющие вершины и , потому что оно наименьшее
Четвёртый шаг
Выбираем наименьшее ребро, которое выходит из уже выбранных вершин
Пятый шаг
Ищем наименьшее ребро и которое не создаст цикл, то есть ребро
Остальные ребра мы не можем взять, так как они создают цикл.
Вычислительная сложность
Сложность алгоритма: , где n - количество вершин (узлов)
Псевдокод
Aлгоритм Прима дерево <- пустой список посещённые узлы <- пустое множество добавляем в список посещённых случайный узел пока не посетим все узлы: мин_ребро <- Выбрать минимальное ребро(рёбра графа, посещённые узлы) добавляем мин_ребро в дерево вернуть дерево Выбрать минимальное ребро(рёбра графа, посещённые узлы) список ребёр <- пусто для ребра в рёбрах графа: если один из узлов ребра посещали то добавляем ребро в список мин_ребро <- минимальное ребро из списка рёбер добавляем узлы мин_ребра в список посещённых отчищаем список рёбер вернуть мин ребро
Реализация на Python
Аннотация: tree_prima - алгоритм Прима edges - список ребер графа nodes_visit - посещенные вершины min_edge - минимальное ребро __return_min_edge - метод, который находит минимальное ребро, которое соединяет посещенные и непосещенные вершины array_edges - список ребер, которые принадлежат множеству посещенных вершин edge - ребро графа
def tree_prima(self): if self._set_adjacency_list: edges = self._edges_graph nodes_visit = set() nodes_visit.add(randint(0, len(self._adjacency_list) - 1)) while len(nodes_visit) != len(self._adjacency_list): min_edge = Graph.__return_min_edge(edges, nodes_visit) self._prima_tree.add_edge(min_edge) return self._prima_tree.edges_tree def __return_min_edge(edges, nodes_visit): array_edges = [] for edge in edges: if (edge.from_node in nodes_visit or edge.to in nodes_visit): if (edge.from_node not in nodes_visit or edge.to not in nodes_visit): array_edges.append(edge) min_edge = min(array_edges, key=Graph.__compare) array_edges.clear() nodes_visit.add(min_edge.from_node) nodes_visit.add(min_edge.to) return min_edge
Олимпиадная реализация на C++
Аннотация: typedef - переопределение имени типа данных r_min_edge - метод, который находит минимальное ребро, которое соединяет посещенные и непосещенные вершины edges - список ребер графа visit - посещенные вершины arr - ребры, которые соеднияют посещенные и непосещенные вершины edge - ребро графа min_edge - минимальное ребро из ребер, которые соеднияют посещенные и непосещенные вершины prima - алгоритм Прима mst - вес мниимального остовного дерева vtx - все вершины графа
typedef vector<int> vi; typedef set<int> si; vi r_min_edge(vector<vi> edges, si visit) { vector<vi> arr; for (vi edge : edges) { if (visit.count(edge[0]) != 0) || (visit.count(edge[1]) != 0)) { if (visit.count(edge[0])) == 0 || (visit.count(edge[1])) == 0) arr.push_back(edge); } }; sort(arr.begin(), arr.end(), comp); vi min_edge = arr[0]; arr.clear(); return min_edge; } int prima(vector<vi> edges, si visit, int vtx) { int mst = 0; while (visit.size() != vtx) { vi min_edge = r_min_edge(edges, visit); mst += min_edge[2]; visit.insert(min_edge[0]); visit.insert(min_edge[1]); }; return mst; }
Продуктовая реализация на C++
Аннотация: Graph::tree_prima - алгоритм Прима Edge - ребро графа edges - список ребер графа node_visit - посещенные вершины min_edge - минимальное ребро Graph::return_min_edge - метод, который находит минимальное ребро, которое соединяет посещенные и непосещенные вершины vector_edges - список ребер, которые принадлежат множеству посещенных вершин
vector<Edge> Graph::tree_prima() { vector<Edge> null_vector; vector<Edge> edges = list_edges_graph; set<int> node_visit; node_visit.insert(get_random_node()); while (node_visit.size() != count_nodes_graph) { Edge min_edge = return_min_edge(edges, node_visit); prima_tree.append_edge(min_edge); node_visit.insert(min_edge.from); node_visit.insert(min_edge.to); }; return prima_tree.get_list_edges_tree(); } Edge Graph::return_min_edge(vector<Edge> edges, set<int> node_visit) { vector<Edge> vector_edges; for (Edge edge : edges) { if (node_visit.count(edge.from) != 0) || (node_visit.count(edge.to) != 0)) { if (node_visit.count(edge.from)) == 0 || (node_visit.count(edge.to)) == 0) vector_edges.push_back(edge); } }; sort(vector_edges.begin(), vector_edges.end(), compare); Edge min_edge = vector_edges[0]; vector_edges.clear(); return min_edge; }
Где используют алгоритмы по поиску МОД
Минимальное остовное дерево и алгоритмы по его поиску используют:
- В картах авиалиний, в которых ребрами отмечены авиарейсы, а веса рёбер означают расстояние или стоимость билетов
- В электронных схемах, где ребра представляют проводники, а веса могут означать длину проводника, его стоимость или время прохода сигнала
- В задачах календарного планирования: веса могут представлять время выполнения задачи или время ожидания её завершения
- В оптимизации маршрута, где ребра представляют путь из одного города в другой, а веса рёбер означают длину пути