最小生成树算法

Boruvka算法求最⼩⽣成树学习了⼀个新的最⼩⽣成树的算法，Boruvka（虽然我不知道怎么读）。

算法思想也是贪⼼，类似于Kruskal。

⼤致是这样的，我们维护图中所有连通块，然后遍历所有的点和边，找到每⼀个连通块和其他连通块相连的最⼩的⼀条边，然后把连通块合并起来，重复这个操作，直到剩下⼀整个连通块，最开始状态是每个点是⼀个单独的连通块。

复杂度是(n+m)longn，因为每次都会合并两个连通块，整个程序进⾏log次操作就会完成，每次操作的复杂度是n+m的。

代码⾮常好理解，我⽤的并查集实现，（然⽽并查集我没有⽤按秩合并，都是细节）。

——by VANE#include<bits/stdc++.h>using namespace std;const int N=5005;const int M=200005;int pre[M<<1],other[M<<1],last[N],l,len[M<<1];int n,m;void add(int x,int y,int z){++l;pre[l]=last[x];last[x]=l;other[l]=y;len[l]=z;}int f[N],mn[2][N];int getfa(int x){return x==f[x]?x:f[x]=getfa(f[x]);}void merge(int x,int y){int fx=getfa(x),fy=getfa(y);f[fx]=fy;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) f[i]=i;for(int i=1;i<=m;++i){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}int ans=0;while(1){memset(mn[0],127,sizeof mn[0]);bool flag=0;for(int i=1;i<=n;++i){for(int p=last[i];p;p=pre[p]){if(getfa(i)!=getfa(other[p]))if(mn[0][getfa(i)]>len[p]){mn[0][getfa(i)]=len[p];mn[1][getfa(i)]=getfa(other[p]);}}}for(int i=1;i<=n;++i){if(mn[0][i]!=mn[0][0]&&getfa(i)!=getfa(mn[1][i])){flag=1;ans+=mn[0][i];merge(i,mn[1][i]);}}if(!flag) break;}for(int i=1;i<n;++i)if(getfa(i)!=getfa(i+1)){puts("orz");return0;}cout<<ans;}。

最⼩⽣成树的Prim算法以及Kruskal算法的证明Prime算法的思路：从任何⼀个顶点开始，将这个顶点作为最⼩⽣成树的⼦树，通过逐步为该⼦树添加边直到所有的顶点都在树中为⽌。

其中添加边的策略是每次选择外界到该⼦树的最短的边添加到树中（前提是⽆回路）。

Prime算法的正确性证明：引理1：对于连通图中的顶点vi，与它相连的所有边中的最短边⼀定是属于最⼩⽣成树的。

引理2：证明：假设最⼩⽣成树已经建成；(vi, vj)是连接到顶点vi的最短边，在最⼩⽣成树中取出vi，断开连接到vi的边，则⽣成树被拆分成1、顶点vi2、顶点vj所在的连通分量（单独⼀个顶点也看作⼀个独⽴的连通分量）3、其余若⼲个连通分量（个数⼤于等于0）三个部分现在要重建⽣成树，就要重新连接之前被断开的各边虽然不知道之前被断开的都是哪⼏条边，但是可以通过这样⼀个简单的策略来重建连接：将vi分别以最⼩的成本逐个连接到这若⼲个互相分离的连通分量；具体来说，就是要分别遍历顶点vi到某个连通分量中的所有顶点的连接，然后选择其中最短的边来连接vi和该连通分量；⽽要将vi连接到vj所在的连通分量，显然通过边(vi, vj)连接的成本最低，所以边(vi, vj)必然属于最⼩⽣成树（如果连接到vi的最短边不⽌⼀条，只要任意挑选其中的⼀条(vi, vj)即可，以上的证明对于这种情况同样适⽤）。

这样我们就为原来只有⼀个顶点vi的⼦树添加了⼀个新的顶点vj及新边(vi, vj)；接下来只要将这棵新⼦树作为⼀个连通⼦图，并且⽤这个连通⼦图替换顶点vi重复以上的分析，迭代地为⼦树逐个地添加新顶点和新边即可。

Kruskal算法：通过从⼩到⼤遍历边集，每次尝试为最⼩⽣成树加⼊当前最短的边，加⼊成功的条件是该边不会在当前已构建的图中造成回路，当加⼊的边的数⽬达到n-1，遍历结束。

Kruskal算法的正确性证明：Kruskal算法每次为当前的图添加⼀条不会造成回路的新边，其本质是逐步地连接当前彼此分散的各个连通分量（单个顶点也算作⼀个连通分量），⽽连接的策略是每次只⽤最⼩的成本连接任意两个连通分量。

xx学院《数据结构与算法》课程设计报告书课程设计题目 PRIM算法求最小生成树院系名称计算机科学与技术系专业（班级）姓名（学号）指导教师完成时间一、问题分析和任务定义在该部分中主要包括两个方面：问题分析和任务定义；1 问题分析本次课程设计是通过PRIM（普里姆）算法，实现通过任意给定网和起点，将该网所对应的所有生成树求解出来。

在实现该本设计功能之前，必须弄清以下三个问题：1．1 关于图、网的一些基本概念1．1．1 图图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。

通常，V（G）和E（G）分别表示图G的顶点集合和边集合。

E（G）也可以为空集。

则图G只有顶点而没有边。

1．1．2 无向图对于一个图G，若边集E（G）为无向边的集合，则称该图为无向图。

1．1．3 子图设有两个图G=（V，E）G’=（V’，）,若V’是V的子集，即V’⊆V ，且E’是E的子集，即E’⊆E，称G’是G的子图。

1．1．4 连通图若图G中任意两个顶点都连通，则称G为连通图。

1．1．5 权和网在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。

把边上带权的图称为网。

如图1所示。

1．2 理解生成树和最小生成树之间的区别和联系1．2．1 生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：V（G’）= V（G）和E（G’）⊆E（G），若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。

1．2．2 最小生成树图的生成树不是唯一的，把具有权最小的生成树称为图G的最小生成树，即生成树中每条边上的权值之和达到最小。

如图1所示。

图1．网转化为最小生成树1．3 理解PRIM（普里姆）算法的基本思想1．3．1 PRIM算法（普里姆算法）的基本思想假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。

matlab 普里姆算法普里姆算法是一种最小生成树算法，用于求解给定图的最小生成树。

该算法基于贪心策略，每次选择当前已选中的点集到未选中的顶点集中距离最近的一条边，将该边所连接的点加入到已选中的点集中。

在实现普里姆算法时，我们需要使用一个优先队列用于存储当前已选中的点集到未选中的顶点集中的边，以及每个顶点到已选中的点集中最小距离。

在每次选取最小距离的边时，我们将该边所连接的点加入到已选中的点集中，并将该点与未选中的点集中的所有点之间的距离加入到优先队列中，同时更新已选中的点集到未选中的顶点集中的最小距离。

该过程重复进行，直到所有的顶点都已经被加入到已选中点集中，最终得到的图就是原图的最小生成树。

下面是使用matlab实现普里姆算法的示例代码：function MST = prim_algorithm(graph)% graph为邻接矩阵，MST为最小生成树的邻接矩阵表示n = size(graph, 1); % 获取图中节点数key = Inf(1,n); % 存储每个顶点与已选中点集的最小距离mst = zeros(n, n); % 存储最小生成树的邻接矩阵表示visited = false(1,n); % 存储每个顶点是否已加入到已选中点集中pq = PriorityQueue(n); % 创建优先队列start = 1; % 从任意一个顶点开始寻找最小生成树key(start) = 0; % 起始点距离已选中点集的最小距离为0pq.insert(start, 0); % 将起始点加入到优先队列中while ~pq.isempty() % 当优先队列非空时进行迭代[u, cost] = pq.deleteMin(); % 选取距离已选中点集最近的边visited(u) = true; % 将选中的顶点加入到已选中点集中if u ~= start % 将当前边加入到最小生成树的邻接矩阵中mst(parent(u), u) = cost;mst(u, parent(u)) = cost;endfor v = 1:n % 更新与已选点集中每个顶点的最小距离if ~visited(v) && graph(u,v) < key(v)parent(v) = u;key(v) = graph(u,v);if pq.contains(v)pq.updatePriority(v, key(v));elsepq.insert(v, key(v));endendendendMST = mst;end该代码中借助matlab的优先队列类PriorityQueue实现了优先队列的功能，其中包括了队列插入、队列删除、队列是否为空、队列中是否包含某元素以及队列中某元素优先级的更新等方法。

克鲁斯卡尔算法构造最小生成树的过程好嘞，今天咱们来聊聊克鲁斯卡尔算法，这个家伙可是构造最小生成树的一把好手。

想象一下，你有一大堆城市，它们之间都有些路，你想用最短的钱和时间把这些路全连起来，这个问题就像是给你一根绳子，让你拼命省着点儿往城市间拉。

你得把所有的路都列出来，然后按照路的长度从短到长来排队。

这样，你就能优先考虑最短的路，节省成本。

比如说，你有一条短短的小路，连接着两个城市，你肯定先铺这条，因为这样最省事，也最省力气。

克鲁斯卡尔算法就是这么个操作，先从最短的路开始连，每连一条路，看看会不会形成环。

形成环的话，就要放弃这条路，换一条次短的，直到你把所有的城市都连起来，但不会形成回路为止。

这样一来，你手里就有了一张最小生成树的地图，这可不是说拿个树枝拼凑的，而是用最合理的方法把所有城市间的联系都搞定了。

有人说这算法像个抠门的人一样，总是要省着点儿花，可这不是省小气，这是精打细算，让每一块钱都花在该花的地方上。

克鲁斯卡尔就像是个精明的理财顾问，给你规划一套最划算的路线，别看他一本正经的，其实心里也有点小聪明，一眼就看出哪条路最值得铺。

想象一下，你手里的路条子越来越多，每一条都是一种选择，你要选对的，不然一不小心可能会给城市之间搞出个乱七八糟的环。

克鲁斯卡尔就像是个懂得捡便宜货的老江湖，他眼光独到，总能一眼看出哪些路最适合先连。

不过，也别以为这算法只能玩玩路，其实它背后的原理，就是避免你贪心，拼命把所有的路都连起来，然后却陷入无限循环。

克鲁斯卡尔就是要让你学会放下那些不合算的选择，每一步都谨慎小心，毕竟谁不想把路走顺当了呢？所以啊，克鲁斯卡尔可不是什么复杂的大师傅，他就是个用心良苦的小算盘，帮你在城市间的小路上玩出了个省时省力的好办法。

他的原则就是小路先连，尽量不要重复造轮子，这样才能保证你在城市之间的行走路线最有效率。

克鲁斯卡尔不仅是个算法，更像是个精明的小商贩，每一分每一毫都能算得清清楚楚，让你的路线规划不但省心，还省力。

数据结构之最⼩⽣成树Prim算法普⾥姆算法介绍 普⾥姆（Prim）算法，是⽤来求加权连通图的最⼩⽣成树算法 基本思想：对于图G⽽⾔，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U⽤于存放G的最⼩⽣成树中的顶点，T存放G的最⼩⽣成树中的边。

从所有uЄU，vЄ(V-U) (V-U表⽰出去U的所有顶点)的边中选取权值最⼩的边(u, v)，将顶点v加⼊集合U中，将边(u, v)加⼊集合T中，如此不断重复，直到U=V为⽌，最⼩⽣成树构造完毕，这时集合T中包含了最⼩⽣成树中的所有边。

代码实现1. 思想逻辑 （1）以⽆向图的某个顶点（A）出发，计算所有点到该点的权重值，若⽆连接取最⼤权重值#define INF (~(0x1<<31)) （2）找到与该顶点最⼩权重值的顶点（B），再以B为顶点计算所有点到改点的权重值，依次更新之前的权重值，注意权重值为0或⼩于当前权重值的不更新，因为1是⼀当找到最⼩权重值的顶点时，将权重值设为了0，2是会出现⽆连接的情况。

（3）将上述过程⼀次循环，并得到最⼩⽣成树。

2. Prim算法// Prim最⼩⽣成树void Prim(int nStart){int i = 0;int nIndex=0; // prim最⼩树的索引，即prims数组的索引char cPrims[MAX]; // prim最⼩树的结果数组int weights[MAX]; // 顶点间边的权值cPrims[nIndex++] = m_mVexs[nStart].data;// 初始化"顶点的权值数组"，// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。

for (i = 0; i < m_nVexNum; i++){weights[i] = GetWeight(nStart, i);}for (i = 0; i < m_nVexNum; i ++){if (nStart == i){continue;}int min = INF;int nMinWeightIndex = 0;for (int k = 0; k < m_nVexNum; k ++){if (weights[k]!= 0 && weights[k] < min){min = weights[k];nMinWeightIndex = k;}}// 找到下⼀个最⼩权重值索引cPrims[nIndex++] = m_mVexs[nMinWeightIndex].data;// 以找到的顶点更新其他点到该点的权重值weights[nMinWeightIndex]=0;int nNewWeight = 0;for (int ii = 0; ii < m_nVexNum; ii++){nNewWeight = GetWeight(nMinWeightIndex, ii);// 该位置需要特别注意if (0 != weights[ii] && weights[ii] > nNewWeight){weights[ii] = nNewWeight;}}for (i = 1; i < nIndex; i ++){int min = INF;int nVexsIndex = GetVIndex(cPrims[i]);for (int kk = 0; kk < i; kk ++){int nNextVexsIndex = GetVIndex(cPrims[kk]);int nWeight = GetWeight(nVexsIndex, nNextVexsIndex);if (nWeight < min){min = nWeight;}}nSum += min;}// 打印最⼩⽣成树cout << "PRIM(" << m_mVexs[nStart].data <<")=" << nSum << ": ";for (i = 0; i < nIndex; i++)cout << cPrims[i] << "";cout << endl;}3. 全部实现#include "stdio.h"#include <iostream>using namespace std;#define MAX 100#define INF (~(0x1<<31)) // 最⼤值(即0X7FFFFFFF)class EData{public:EData(char start, char end, int weight) : nStart(start), nEnd(end), nWeight(weight){} char nStart;char nEnd;int nWeight;};// 边struct ENode{int nVindex; // 该边所指的顶点的位置int nWeight; // 边的权重ENode *pNext; // 指向下⼀个边的指针};struct VNode{char data; // 顶点信息ENode *pFirstEdge; // 指向第⼀条依附该顶点的边};// ⽆向邻接表class listUDG{public:listUDG(){};listUDG(char *vexs, int vlen, EData **pEData, int elen){m_nVexNum = vlen;m_nEdgNum = elen;// 初始化"邻接表"的顶点for (int i = 0; i < vlen; i ++){m_mVexs[i].data = vexs[i];m_mVexs[i].pFirstEdge = NULL;}char c1,c2;int p1,p2;ENode *node1, *node2;// 初始化"邻接表"的边for (int j = 0; j < elen; j ++){// 读取边的起始顶点和结束顶点p1 = GetVIndex(c1);p2 = GetVIndex(c2);node1 = new ENode();node1->nVindex = p2;node1->nWeight = pEData[j]->nWeight;if (m_mVexs[p1].pFirstEdge == NULL){m_mVexs[p1].pFirstEdge = node1;}else{LinkLast(m_mVexs[p1].pFirstEdge, node1);}node2 = new ENode();node2->nVindex = p1;node2->nWeight = pEData[j]->nWeight;if (m_mVexs[p2].pFirstEdge == NULL){m_mVexs[p2].pFirstEdge = node2;}else{LinkLast(m_mVexs[p2].pFirstEdge, node2);}}}~listUDG(){ENode *pENode = NULL;ENode *pTemp = NULL;for (int i = 0; i < m_nVexNum; i ++){pENode = m_mVexs[i].pFirstEdge;if (pENode != NULL){pTemp = pENode;pENode = pENode->pNext;delete pTemp;}delete pENode;}}void PrintUDG(){ENode *pTempNode = NULL;cout << "邻接⽆向表:" << endl;for (int i = 0; i < m_nVexNum; i ++){cout << "顶点:" << GetVIndex(m_mVexs[i].data)<< "-" << m_mVexs[i].data<< "->"; pTempNode = m_mVexs[i].pFirstEdge;while (pTempNode){cout <<pTempNode->nVindex << "->";pTempNode = pTempNode->pNext;}cout << endl;}}// Prim最⼩⽣成树void Prim(int nStart){int i = 0;int nIndex=0; // prim最⼩树的索引，即prims数组的索引char cPrims[MAX]; // prim最⼩树的结果数组int weights[MAX]; // 顶点间边的权值cPrims[nIndex++] = m_mVexs[nStart].data;// 初始化"顶点的权值数组"，// 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。