最小生成树

朴素prim（普利姆）算法
一般用这个算法解决稠密图，用邻接矩阵来存图。是无向边所以就是存两条反向的单向边，来表示。
思路和dijkstra算法差不多。
开一个n次遍历，每次遍历都从还没加到集合中的点选一个到集合距离最小的点，dijkstra算法求的是最短路，所以是到原点，prim算法是求一个所有边都是最小的树，即最小生成树，用集合来维持这个树，所以是到集合距离最小的点。
到集合的距离就是说每个点到这个集合中的某一个点的边。之后要求最小生成树一般不是把树给输出而是将其边的合输出。所以要有一个变量去存。一般存的时候先是判断是不是为第一次，因为第一次就是起点，其到集合的距离为0，之后在更新之前存。因为如果存在自环且权重为负，或者权重比本身到集合的距离小，那么在更新之后可能会有disk[t] = d[t] [t] 的这种情况，然后disk[t]的值就会发生变化，所以为了避免这种情况，一般都是将加入答案的操作放在更新之前。
判断有没有最小生成树，一开始将每一个点的距离初始化为无穷，如果就是在某一次遍历（除了第一次）中取得的点的距离为无穷，就是说明当前集合之外的点离集合最短的距离为无穷，也就是集合中没有一个点有和剩余的点向连的边，所以这个图就没有最小生成树。

例题：

Prim求最小生成树

给定一个 n个点 m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 VV 表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由 V中的全部 n个顶点和 E中 n−1 条边构成的无向连通子图被称为 G的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G的最小生成树。
输入格式
第一行包含两个整数 n和 m。
接下来 m行，每行包含三个整数u,v,w，表示点 u和点 v之间存在一条权值为 w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围 1≤n≤500, 1≤m≤105, 图中涉及边的边权的绝对值均不超过10000。
输入样例：

输出样例：

kruskal（克鲁斯卡尔）算法
利用到并查集的思想。基本思路就是先将每条边按照权重排序，然后维持一个集合，之后枚举每条边，假设枚举到的边的两个点不连通就将他们连起来，就是放到一个集合中，然后将权重加到答案中（因为从小到大枚举边，所以假设存在树结构，那么每条边一定是最小的，也就是实际上构成了最小生成树）。在存储边的时候因为只要能够排序就行，所以可以用结构体来存。
为了在排序的时候实现根据权重来排序，需要重载一下小于号
对于并查集在使用的时候需要初始化每个点的父节点为本身

bool operator < (const edge &W)const
{
    return w < W.w;
}

为了判断是否存在最小生成树，可以再新建一个变量cot，表示集合中的边数，当进行一次连通操作时（也就是并集）cot++，之后如果在所有边都枚举完之后，cot < n - 1 说明有点没有加入集合（一共 n 个点，应该一共 n - 1条边）那么就不存在最小生成树，反之等于 n - 1 时就存在，然后输出res
例题：

Kruskal求最小生成树

给定一个 n个点 m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E)，其中 VV 表示图中点的集合，EE 表示图中边的集合，n=|V|，m=|E|。
由 V中的全部 n个顶点和 E中 n−1 条边构成的无向连通子图被称为 G的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G的最小生成树。
输入格式
第一行包含两个整数 n和 m。
接下来 m行，每行包含三个整数u,v,w，表示点 u和点 v之间存在一条权值为 w的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围 1≤n≤105 , 1≤m≤2∗1e5 , 图中涉及边的边权的绝对值均不超过 1000。
输入样例：

输出样例：

当前页面是本站的「Baidu MIP」版。发表评论请点击：完整版 »