最小生成树算法-C++算法笔记（十七）图论（三、最小生成树）

【问题导入】

有一个乡镇准备给所有村子换新的光缆，光缆的价格与距离成正比，有些村子能直接互相连接，有些不能，给出能连接的村子的距离，请问怎么布局光缆使得总花费最少。

分析：显然村子可以看做是一个图的模型，但是图有多条边，这个问题需要找到能连接所有村庄的一棵树，并且是边权的边权最小的树。

将n个点的图删掉一些多余边，删掉过程中所有点依然连通，最后使图变成一棵树，这棵树叫做图的生成树。

图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树(Minimum Spanning Tree，MST) ；

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的 n − 1条边；

对于一个带权 (假定每条边上的权均为大于零的数) 连通无向图 G 中的不同生成树，其每棵树的所有边上的权值之和也可能不同；

简单来说，对于一个有 n 个点的图，边一定是大于等于 n − 1 条的，最小生成树就是在这些边中选择 n − 1条出来连接所有的 n个点，且这n − 1 n 条边的边权之和是所有方案中最小的；

图的最小生成树一般有两种算法：

一、prim（普利姆算法）

算法思路：

①任意选择一个顶点，将其放入点集合中；下图选的顶点为A;

②将与A顶点相连的边放入待选边集合中，如下图的A-B(6) A-F(1) A-E(5)所示；

③选择一个权值最小的边放入边集合中，下图中是A-F(1);将该边所连的顶点F放入点集合中;

④将与F点相连的边放入待选边集合中，如F-B(2) F-E(9) F-C(8) F-D(4)，重复上面2~3步的过程，直到所有的点都被包含在点集合中最小生成树算法，更新带待选边的权值。

⑤普利姆算法适用于稠密的图，即边数较多的图，时间复杂度o(n^2);

最小生成树算法_小生小生我怕怕哎呀我的妈_算法导论回溯算法

详细过程图：

例题：P3366 最小生成树

参考代码：

#include #include using namespace std;struct node{  int t;  int z;};int f[5005];int d[5005];vector mp[5005];const int INF=1<<30;int main(){  int n,m,x,y,z,s=0;  node k;  cin>>n>>m;  for(int i=0;i<m;i++)  {    cin>>x>>y>>z;    k.t=x;k.z=z;    mp[y].push_back(k);    k.t=y;    mp[x].push_back(k);  }  for(int i=1;i<=n;i++)  {    d[i]=INF;  }  d[1]=0;  while(1)  {    int x=INF;    int u=0;    for(int i=1;i<=n;i++)    {      if(d[i]<x&&f[i]==0)      {        x=d[i];        u=i;      }    }    if(!u) break;    f[u]=1;    s+=x;    for(int i=0;i<mp[u].size();i++)    {      if(f[mp[u][i].t]==0 && mp[u][i].z<d[mp[u][i].t])        d[mp[u][i].t]=mp[u][i].z;    }  }  for(int i=1;i<=n;i++)  {    if(d[i]==INF)    {      cout<<"orz";      return 0;    }  }  cout<<s<<endl;  return 0;}

二、Kruskal算法（克鲁斯卡算法）

算法思想：kruskal算法是一种贪心算法，每次找到剩余边中的最小边最小生成树算法，如果这个边能选择（这个边的两个点不连通），则选择这条边。

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；

2. 把图中的n个顶点看成独立的n棵树组成的森林；

3. 按权值从小到大选择边，所选的边连接的两个顶点ui,vi 。ui,vi,应属于两棵不同的树，则成为最小生成树的一条边，并将这两棵树合并作为一棵树。

4. 重复(3),直到所有顶点都在一棵树内或者有n-1条边为止。

判断两个点属于不同的树我们选择使用并查集（参考）

参考代码：

//P3366#include #include using namespace std;struct edge{  int from;  int to;  int cost;}lines[400005];int fa[5005],n,m,x,y,c,ans,cnt;int find(int x){  while(x!=fa[x]) x=fa[x]=fa[fa[x]];  return x;}bool bing(int x,int y){  int xx=find(x);  int yy=find(y);  if(xx==yy) return false;  fa[xx]=yy;  return true;}bool cmp(edge x,edge y){  return x.cost<y.cost;}void kruskal(){  sort(lines,lines+m,cmp);  for(int i=0;i<m;i++)  {    edge t=lines[i];    if(bing(t.from,t.to))    {        ans+=t.cost;      cnt++;    }    if(cnt==n-1)    {      cout<<ans<<endl;      return;    }  }  cout<<"orz"<<endl;  return ;}int main(){  cin>>n>>m;  for(int i=1;i<=n;i++)    fa[i]=i;  for(int i=0;i<m;i++)  {    cin>>lines[i].from>>lines[i].to>>lines[i].cost;  }  kruskal();  return 0;}