Минимальное остовное дерево — это остовное дерево с наименьшим весом в связном взвешенном неориентированном графе.
Каждый узел подключен, и общая стоимость подключения минимальна.
Связанные приложения
Кабельная разводка
веб-дизайн
схемотехника
Минимальное остовное дерево в основном предназначено для:
Для взвешенных неориентированных графов
Для связанных графов
Для несвязных графов можно найти все минимальные остовные деревья, которые являются связными компонентами, чтобы сформировать минимальный лес.
шаг
Найдите ребро V-1
Соединить V вершин
Минимальный общий вес
Теорема о разрезе: свойство разреза
Определение сегментации
Разделить узлы графа на две части, называемые разрезом
Синяя и красная части образуют раскол.
Определение пересекающихся кромок
Если две конечные точки ребра принадлежат разным сторонам разреза (Cut), такое ребро называется пересекающимся ребром (Crossing Edge).
Теорема сегментации:
При любом разбиении ребро с наименьшим весом среди пересекающихся ребер должно принадлежать минимальному остовному дереву.
Lazy Prim
Выберите v-1 из всех ребер.
Найдите наименьшее из четырех поперечных ребер
Минимальная реализация кучи
После добавления наименьшего ребра. сделать новый разрез
Продолжайте добавлять точки с наименьшим сквозным ребром, пока не будут введены все вершины (пока, наконец, не будут посещены все узлы).
Ленивый: Хоть и не поперечная кромка, но не выбрасывается.
int main() {
string filename = "testG1.txt";
int V = 8;
SparseGraph<double> g = SparseGraph<double>(V, false);
ReadGraph<SparseGraph<double>, double> readGraph(g, filename);
// Test Lazy Prim MST
cout<<"Test Lazy Prim MST:"<<endl;
LazyPrimMST<SparseGraph<double>, double> lazyPrimMST(g);
vector<Edge<double>> mst = lazyPrimMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<lazyPrimMST.result()<<endl;
cout<<endl;
// Test Prim MST
cout<<"Test Prim MST:"<<endl;
PrimMST<SparseGraph<double>, double> primMST(g);
mst = primMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<primMST.result()<<endl;
cout<<endl;
return 0;
}
результат
Test Lazy Prim MST:
0-7: 0.16
7-1: 0.19
0-2: 0.26
2-3: 0.17
7-5: 0.28
5-4: 0.35
2-6: 0.4
The MST weight is: 1.81
временная сложность
O(ElogE)
###Оптимизация алгоритма Prim
Проблемы с Ленивым Примом
Все ребра попадают в минимальную кучу, а ребра между посещенными узлами на самом деле незначительны (ребра в минимальной куче больше не являются пересекающимися ребрами).
Просто рассмотрите наименьшее сквозное ребро, которое соединяется с узлом.
Поддерживать структуру данных:
Кратчайшее сквозное ребро, связанное с каждым узлом.
Оптимизация основного алгоритма
Реализация кода (O(ElogV)
//
// Created by liuyubobobo on 9/26/16.
//
#ifndef INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_PRIMMST_H
#define INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_PRIMMST_H
#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
#include "IndexMinHeap.h"
using namespace std;
template<typename Graph, typename Weight>
class PrimMST{
private:
Graph &G;
vector<Edge<Weight>> mst;
bool* marked;
IndexMinHeap<Weight> ipq;
vector<Edge<Weight>*> edgeTo; //存储节点的最短横切边。
Weight mstWeight;
void visit(int v){
assert( !marked[v] );
marked[v] = true;
typename Graph::adjIterator adj(G,v);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){
int w = e->other(v);
if( !marked[w] ){
if( !edgeTo[w] ){
edgeTo[w] = e;
ipq.insert(w, e->wt());
}
else if( e->wt() < edgeTo[w]->wt() ){
edgeTo[w] = e;
ipq.change(w, e->wt());//最小索引堆才有change操作
}
}
}
}
public:
// assume graph is connected
PrimMST(Graph &graph):G(graph), ipq(IndexMinHeap<double>(graph.V())){
assert( graph.E() >= 1 );
marked = new bool[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
marked[i] = false;
edgeTo.push_back(NULL);
}
mst.clear();
visit(0);
while( !ipq.isEmpty() ){
int v = ipq.extractMinIndex();
assert( edgeTo[v] );
mst.push_back( *edgeTo[v] );
visit( v );
}
mstWeight = mst[0].wt();
for( int i = 1 ; i < mst.size() ; i ++ )
mstWeight += mst[i].wt();
}
~PrimMST(){
delete[] marked;
}
vector<Edge<Weight>> mstEdges(){
return mst;
};
Weight result(){
return mstWeight;
};
};
#endif //INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_PRIMMST_H
Алгоритм Крускала
определение
Алгоритм Крускала — это алгоритм поиска минимального остовного дерева, опубликованный Джозефом Крускалом в 1956 году. Алгоритм Прима и алгоритм Борувки используются для решения одной и той же задачи. Все три алгоритма являются приложениями жадного алгоритма. В отличие от алгоритма Борувки, алгоритм Крускала также эффективен, когда в графе есть ребра с одинаковым весом.
шаг
Создайте новый граф G, который имеет те же узлы, что и исходный граф, но без ребер.
Отсортировать все ребра в исходном графе по весу от меньшего к большему
Начиная с ребра с наименьшим весом, если две вершины, соединенные этим ребром, не находятся в одной компоненте связности в графе G, добавляем это ребро в граф G
Повторяйте 3, пока все узлы графа G не окажутся в одном компоненте связности.
Определить, образует ли узел кольцо
Используйте Union Find, чтобы быстро идентифицировать кольца
Нужно только судить, совпадают ли корни двух вершин найденного ребра, если они совпадают, значит, это уже связный граф.
Код
// Kruskal算法
template <typename Graph, typename Weight>
class KruskalMST{
private:
vector<Edge<Weight>> mst; // 最小生成树所包含的所有边
Weight mstWeight; // 最小生成树的权值
public:
// 构造函数, 使用Kruskal算法计算graph的最小生成树
KruskalMST(Graph &graph){
// 将图中的所有边存放到一个最小堆中
MinHeap<Edge<Weight>> pq( graph.E() );
for( int i = 0 ; i < graph.V() ; i ++ ){
typename Graph::adjIterator adj(graph,i);
for( Edge<Weight> *e = adj.begin() ; !adj.end() ; e = adj.next() )
//只存一条边中的一个节点
if( e->v() < e->w() )
pq.insert(*e);
}
// 创建一个并查集, 来查看已经访问的节点的联通情况
UnionFind uf = UnionFind(graph.V());
while( !pq.isEmpty() && mst.size() < graph.V() - 1 ){
// 从最小堆中依次从小到大取出所有的边
Edge<Weight> e = pq.extractMin();
// 如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边
if( uf.isConnected( e.v() , e.w() ) )
continue;
// 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通
mst.push_back( e );
uf.unionElements( e.v() , e.w() );
}
mstWeight = mst[0].wt();
for( int i = 1 ; i < mst.size() ; i ++ )
mstWeight += mst[i].wt();
}
~KruskalMST(){ }
// 返回最小生成树的所有边
vector<Edge<Weight>> mstEdges(){
return mst;
};
// 返回最小生成树的权值
Weight result(){
return mstWeight;
};
};
// 测试Kruskal算法
int main() {
string filename = "testG1.txt";
int V = 8;
SparseGraph<double> g = SparseGraph<double>(V, false);
ReadGraph<SparseGraph<double>, double> readGraph(g, filename);
// Test Lazy Prim MST
cout<<"Test Lazy Prim MST:"<<endl;
LazyPrimMST<SparseGraph<double>, double> lazyPrimMST(g);
vector<Edge<double>> mst = lazyPrimMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<lazyPrimMST.result()<<endl;
cout<<endl;
// Test Prim MST
cout<<"Test Prim MST:"<<endl;
PrimMST<SparseGraph<double>, double> primMST(g);
mst = primMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<primMST.result()<<endl;
cout<<endl;
// Test Kruskal MST
cout<<"Test Kruskal MST:"<<endl;
KruskalMST<SparseGraph<double>, double> kruskalMST(g);
mst = kruskalMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<kruskalMST.result()<<endl;
return 0;
}
Дополнительные мысли об алгоритмах
Lazy Prim O( ElogE )
Prim O( ElogV )
Kruskal O( ElogE )
Алгоритм Высоцкого:
В соответствии с конкретной реализацией алгоритма за раз выбирается одно ребро.
На данный момент в графе есть несколько минимальных остовных деревьев.
Ребро постепенно добавляется к остовному дереву
Как только кольцо сформировано, удалите ребро с наибольшим весом в кольце.
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут нажать «Нравится» / «Подписаться», ваша поддержка — самая большая поддержка для меня.