最小生成树

Kruskal算法：（找最小生成树）

首先按照边的长度由小到大排序

每次选出最小的与之前选过的判断在不在同一集合（并查集）

如果m条边都枚举完还没连到n-1条边，则无解。

时间复杂度 O(mlogm) (m为边的数量)

代码：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const int H=10005;
struct node{
    int a,b,len;
};
node edge[H];//保存所有边的信息 
int n,m,fa[N];//fa存i的父亲节点，n为顶点数，m为边数 
bool cmp(node a,node b){return a.len<b.len;}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].len);//读入图 
    for(int i=1;i<=n;i++)//初始化并查集 
        fa[i]=i;
    sort(edge+1,edge+1+m,cmp);//将边的权值从小到大排序 
}
int getfather(int x){//并查集，用来判断两个顶点是否属于同一个生成树（集合） 
    if(x!=fa[x])
        fa[x]=getfather(fa[x]);
    return fa[x];
}
void kruskal(){
    int x,y,k=0,cnt=0,tot=0;
    //k为当前边的编号，tot统计最小生成树的边权总和
    //cnt统计进行了几次合并，n-1次合并后就得到了最小生成树 
    while(cnt<n){//n个点构成的生成树只有n-1条边 
        k++;
        x=getfather(edge[k].a);
        y=getfather(edge[k].b);
        if(x!=y){
            fa[x]=y;//合并 
            tot=tot+edge[k].len;
            cnt++;
        }
    }
    printf("%d\n",tot);
}
int main(){
   init();
   kruskal();
   return 0;
}

prim算法：（找最小生成树）

1.任选一个点，加入生成树集合

2.在未加入的生成书的点中，找出里生成树距离最近的一个点，将其加入生成树。

3.重复执行2，直到所有点都加入了生成树，否则无解

时间复杂度O(n^2）

代码：

const int N=105;
int dis[N],path[N],map[N][N],minn;//注：为了节约篇幅采用暴力存图。
//path[i]:i点与哪个点相连  
//dis[j]:j点到生成树的距离 
void prim(int x){//任选x个点 
    for(int i=1;i<=n;i++){
        dis[i]=map[i][x];
        path[i]=x;
    }
    for(int i=1;i<n;i++){
        minn=inf;
        for(int j=1;j<=n;j++)
            if(dis[j] && dis[j]<minn){
                minn=dis[j];
                k=j;
            }
        dis[k]=0;
        for(int j=1;j<=n;j++)
            if(dis[j]>map[j][k]){
                dis[j]=map[j][k];
                path[j]=k; 
            } 
    }
}

O(n^2）的时间复杂度有点高

那么怎么优化呢？

跟迪杰斯特拉一样：

存储优化，小根堆

完美！！！

输出最短路径总长度

for(int i=1;i<=n;i++)
    if(path[i]!=i)
        tot+=map[i][path[i]];
printf("%d",tot);