最小树次小树模板

最小生成树

两种算法,Kruskal 和 Prim ;

Kruskal 是针对于稀疏图的,因为他的复杂度是跟边有关系的;
先sort一便,然后用并查集加边就行了,简单没什么说的.

Prim 是针对于稠密图的,这个算法自己很少用,就是每次都找到加入后边最小的那个点

加进来就行了,前两天hdu4756逼得我不得不看这个算法.


次小树

次小树自己常用的也是两种算法,不知道名字,可能算不上是什么算法吧
先说一下思想吧,次小树其实就是先找到一颗最小树,然后删除其中一条边,找到一个最有

的可以连接两个集合的边就行了,更新到最后就是次小树,其实也可以这样,先跑一边最小树,
然后枚举所有不是最小树上的边,想下,如果这条边加在最小树里肯定会产生环,所以直接找

到环中最长的边(该边除外)减去就行了,这样更新到最后也是次小树,这就是第二种方法,第

一种方法中的找最小可以用树形dp去优化,如果暴力时间复杂度肯能会到o(n^3);

下面是模板

Kruskal

#include<algorithm>

#define MAX_EDGE 10000//边的最大个数
#define MAX_NODE 1000//点的最大个数

using namespace std;

typedef struct
{
int a ,b;
double dis;
}EDGE;

EDGE edge[MAX_EDGE]; //把边存到这里
int mer[MAX_EDGE];

bool camp(EDGE a ,EDGE b)
{
return a.dis < b.dis;
}

int finds(int x)
{
return x == mer[x] ? x : mer[x] = finds(mer[x]);
}

struct KRUSKAL
{
double Kruskal (int edge_n ,int node_n)//边和点的个数
{
double ans;
sort(edge + 1 ,edge + edge_n + 1 ,camp);
for(int i = 0 ;i <= node_n ;i ++) mer[i] = i;
ans = 0;
for(int i = 1 ;i <= edge_n ;i ++)
{
int x = finds(edge[i].a);
int y = finds(edge[i].b);
if(x == y) continue;
mer[x] = y;
ans += edge[i].dis;
}
return ans;
}
}K;

Prim

struct PRIM //从0开始用
{
double d[N];int vis[N];
bool mp[N][N]; //标记最小生成树上的边
double ans;//最小树
int n;//点的个数记得初始化 ***
double dis[N][N]; // 距离记得初始化 *****

void prim()
{
for(int i=0;i<n;i++)
{
vis[i]=0;
d[i]=dis[0][i];
}
vis[0]=-1;
ans=0;
memset(mp,0,sizeof(mp));
for(int i=1;i<n;i++)
{
double Min= inf;
int node=-1;
for(int j=0;j<n;j++)
{
if(vis[j]!=-1 && d[j]<Min)
{
node=j;
Min=d[j];
}
}

ans+=Min; //printf("%lf " ,ans);
mp[vis[node]][node]=mp[node][vis[node]]=1;
//add(vis[node],node); // 建树
vis[node]=-1;

for(int j=0;j<n;j++)
{
if(vis[j]!=-1 && d[j]>dis[node][j])
{
vis[j]=node;
d[j]=dis[node][j];
}
}
}
}
}P;

剩下的那两个还没有总结好模板,最近也正在学,学完在总结补上吧..

最小树 次小树 模板

最小树次小树模板