最小生成树
基本概念prim算法思想算法步骤时间复杂度图例描述模板优化
Kruskal算法思想算法步骤并查集
时间复杂度图例描述模板
基本概念
在无向图中，连通且不含环的图称为树。
生成树的定义 在一个v个点的无向连通图中，取其中v-1条边，并连接所有的顶点，所得到的子图称为原图的一棵生成树；最小生成树 在一个带权的无向连通图中，各边权和最小的一棵生成树即为原图的最小生成树；最小边原则 图中权值最小的边（如果唯一的话）一定在最小生成树上；唯一性原则 对于一个图G，如果图中的边权值都不相同，则图的最小生成树是惟一的，反之不然；
prim算法
思想
prim算法是一种贪心算法她最初将无向联通图G中所有顶点V分成两个顶点集合VA和VB。在计算过程中VA中的点为已经选好的连接入生成树的点，否则属于VB。最开始的时候VA只包含任意选取的图G中的一个点u，其余的点属于VB，每次添加一个VB中的点（集合VB到集合VA中距离最小的那个点）到集合VA。直到V个顶点全部属于VA，算法结束。显然出发点不同，最小生成树的形态就不同，但边权和的最小值是唯一的。
算法步骤
选定图中的任意一个顶点V0，从V0开始生成最小数：
初始化dis[V0]=0，其他点的距离值dis[i]为极大值。其中dis[i]表示集合VB中的点到集合VA中的点的距离值。经过N次以下步骤，最后得到最小生成树： ①. 选择一个未被标记的点k，并且dis[k]的值是最小的； ②.标记点k进入集合VA； ③.以k为中心点，修改未标记点j，即VB中的点到VA的距离值；得到最小生成树。
伪代码 for(int i=1;i<=n;i++) dis[i]=inf; dis[1]=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) 找dis[j]最小&&vis[j]==0的点j， vis[j]=1; 更新j->k的dis[k];
时间复杂度
最小边、权的数据结构时间复杂度（总计）
邻接矩阵、搜索O(V^2)二叉堆、邻接表O((V + E) log(V)) = O(E log(V))斐波那契堆、邻接表O(E + V log(V))
通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(ElogV)，其中E为连通图的边数，V为顶点数。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)，这在连通图足够密集时（当E满足Ω（VlogV）条件时），可较显著地提高运行速度。
图例描述
图例说明不可选可选已选(VA)
此为原始的加权连通图。每条边一侧的数字代表其权值。---顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。C, GA, B, E, FD下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。C, GB, E, FA, D算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。CB, E, GA, D, F在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。点E最近，因此将顶点E与相应边BE高亮表示。无C, E, GA, D, F, B这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。无C, GA, D, F, B, E顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。无GA, D, F, B, E, C现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。无无A, D, F, B, E, C, G
模板
#include<iostream>
using namespace std
;
const int maxn
=1<<31-1;
int map
[505][505],vis
[505],dis
[505],n
,m
,ans
;
void read()
{
cin
>>n
>>m
;
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
map
[i
][j
]=maxn
;
for(int i
=1;i
<=m
;i
++)
{
int x
,y
,w
;
cin
>>x
>>y
>>w
;
map
[x
][y
]=map
[y
][x
]=w
;
}
}
void prim(int x
)
{
int k
;
for(int i
=1;i
<=n
;i
++) dis
[i
]=maxn
;
dis
[x
]=0;
for(int i
=1;i
<=n
;i
++)
{
int mint
=maxn
;
for(int j
=1;j
<=n
;j
++)
if(vis
[j
]==0&&mint
>dis
[j
])
{
k
=j
;
mint
=dis
[j
];
}
vis
[k
]=1;
ans
+=dis
[k
];
for(int j
=1;j
<=n
;j
++)
if(vis
[j
]==0) dis
[j
]=min(dis
[j
],map
[k
][j
]);
}
}
int main()
{
read();
prim(1);
cout
<<ans
<<endl
;
return 0;
}
优化
思考：怎样快速找到权值最小的边？——我们需要借助于堆。 堆：堆是一种特殊的二叉完全树。它以一定的偏序来保存所有节点。即只需要满足父节点大于两个子节点，而子节点之间没有要求。 堆有两种：大顶堆和小顶堆。小顶堆中每个节点的优先级小于或者等于它的子节点；大顶堆则相反。 我们在构建一个堆，总是从上到下，从左到右的插入新点，同时进行编号。
插入：将新节点放到堆的末尾 void push(int w) ｛ heap[++cnt]=w;cnt指向堆末尾的点 heapup(cnt);//要保证构建的堆满足偏序的要求，必须要进行上调操作。 ｝
上调：如果新插入点小于父节点。 void heapup(int x) ｛ while(x>1)//当它不是根节点 if(heap[x>>1]>heap[x])//如果它的父节点比它还大 swap(heap[x>>1],heap[x]); x>>=1; else break; ｝
删除堆顶元素： int pop() ｛ int ret=heap[1]； swap(heap[1],heap[cnt]);//顶点后末尾互换 cnt–;//删除末尾 heapdown(1);//要保证新的顶点最小，必须完成下调操作。 return ret; ｝
下调：如果父节点大于儿子节点 void heapdown(int x) ｛ int k; while((x<<1)<=cnt)//当它的左儿子在堆中 if((x<<1)==cnt||heap[x<<1]]<heap[(x<<1)+1])//如果左儿子是末尾或者左儿子小于右儿子 k=x<<1;//选择左儿子 else k=(x<<1)+1;//否则选择右儿子 if(heap[x]>heap[k])//如果它大于儿子 swap(heap[x],heap[k]); x=k; else break ｝
Kruskal算法
思想
kruskal算法也是一种贪心算法，它是将边按权值排序，每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中，反复操作，直到加入了n-1条边。
算法步骤
是给所有边按照从小到大的顺序排列。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考查每条边(u,v)。 情况1：u和v在同一个连通分量中，那么加入(u, v)后会形成环，因此不能选择。 情况2：如果u和v在不同的连通分量，那么加入(u, v)一定是最优的。为什么呢？下面用反证法——如果不加这条边能得一个最优解T，则T+(u, v)一定有且只有一个环，而且环中至少有一条边(u’ , v’)的权值大于或等于(u,v)的权值。删除该边后，得到的新树T’=T+(u, v)-(u’,v’)不会比T更差。因此，加入(u, v)不会比不加入差。重复2的操作，直到生成树T中只包含n-1条边。否则当遍历完所有边后，选取不到n-1条边，表示最小生成树不存在。
伪代码 sort(e+1,e+m+1); 初始化MST=NULL; 初始化各点各自为一个集合； for(int i=0;i<m;i++) { if(e[i].u和e[i].v不在一个集合) { 将e[i]加入MST； 合并e[i].u和e[i].v所在的集合; } }
该算法中关键在于解决判断u，v是否在同一集合和将其合并的操作，这里我们使用一种简单高效的方法：并查集。
并查集
一位大佬的理解：指路。 可以把每个连通分量看成一个集合，该集合包含了连通分量中的所有点。这些点两两连通，而具体的连通方式无关紧要，就好比集合中的元素没有先后顺序之分，只有“属于”和“不属于”的区别。在图中，每个点恰好属于一个连通分量，对应到集合表示中，每个元素恰好属于一个集合。换句话说，图的所有连通分量可以用若干个不相交集合来表示。 并查集的精妙之处在于用树来表示集合。例如，若包含点1，2，3，4，5，6的图有3个连通分量{1,3}、{2,5,6}、{4}，则需要用3棵树来表示。这3棵树的具体形态无关紧要，只要有一棵树包含1、3两个点，一棵树包含2、5、6这3个点，还有一棵树只包含4这一个点即可。规定每棵树的根结点是这棵树所对应的集合的代表元（representative）。 如果把x的父结点保存在p[x]中（如果x没有父结点，则p[x]等于x），则不难写出“查找结点x所在树的根结点”的递归程序：int find(int x) { p[x] == x ? x : find(p[x]); }，通俗地讲就是：如果p[x]等于x，说明x本身就是树根，因此返回x；否则返回x的父结点p[x]所在树的树根。 问题来了：在特殊情况下，这棵树可能是一条长长的链。设链的最后一个结点为x，则每次执行find(x)都会遍历整条链，效率十分低下。看上去是个很棘手的问题，其实改进方法很简单。既然每棵树表示的只是一个集合，因此树的形态是无关紧要的，并不需要在“查找”操作之后保持树的形态不变，只要顺便把遍历过的结点都改成树根的子结点，下次查找就会快很多了，如图所示。
时间复杂度
平均时间复杂度为O(|E|log|E|)，其中E是图的边集。
图例描述
图例说明不可选可选已选边
此为原始的加权连通图。每条边一侧的数字代表其权值。---所有存在的边都可以选-所有边-在所有存在的边中，点1到点2的距离最小，所以将边1->2加入生成树中。所以对于下一次可选的边就有：1->4,1->3,2->3,2->5。4->3,4->5,5->31->4,1->3,2->3,2->51->2在可选边中3->5距离最小，所以将边3->5加入生成树，下一次的可选边就有:1->3,1->4,2->3,3->4,2->5,4->5-1->3,1->4,2->3,3->4,2->5,4->53->5,1->2在可选边中3->4距离最小，所以将边3->4加入生成树，下一次的可选边就有:1->3,1->4,2->3,2->5,4->5-1->3,1->4,2->3,2->5,4->53->5,1->2,3->4在可选边中4->5距离最小，但是若将边4->5加入生成树则构成环，并不是一棵树，所以选择次小的边2->3加入生成树。所以此例中最小生成树和为194->5,2->5,1->3,1->4-2->3,3->5,1->2,3->4
模板
#include<iostream>
#include<algorithm>
using namespace std
;
struct edge
{
int u
,to
,w
;
}e
[200010];
int n
,m
,ans
,fa
[5010];
bool cmp(const edge
&a
,const edge
&b
)
{
return a
.w
<b
.w
;
}
int find(int x
)
{
if(fa
[x
]==x
) return x
;
else return fa
[x
]=find(fa
[x
]);
}
void print()
{
int x
,y
;
x
=find(1);
for(int i
=2;i
<=n
;i
++)
{
y
=find(i
);
if(x
!=y
) {cout
<<"orz";return;}
}
cout
<<ans
;
}
void kruskal()
{
sort(e
+1,e
+m
+1,cmp
);
for(int i
=1;i
<=n
;i
++)
fa
[i
]=i
;
for(int i
=1;i
<=m
;i
++)
{
int x
,y
;
x
=find(e
[i
].u
);
y
=find(e
[i
].to
);
if(x
!=y
)
{
fa
[x
]=y
;
ans
+=e
[i
].w
;
}
}
}
int main()
{
cin
>>n
>>m
;
for(int i
=1;i
<=m
;i
++)
cin
>>e
[i
].u
>>e
[i
].to
>>e
[i
].w
;
kruskal();
print();
return 0;
}
参考资料：《信息学奥赛一本通提高篇》《算法竞赛入门经典》《百度百科》
