图的算法专题——最小生成树

概要：

1. Prim算法
2. Kruskal算法

---

 

1、Prim算法

算法流程：

（1）对图G（V,E）设置集合S来存放已被并入的顶点，然后执行n次（2）（3）

（2）每次从未并入顶点集合中选择与集合S最近的一个顶点，访问u并将其加入集合S，同时把这条离集合S最近的边加入最小生成树中。

（3）优化松弛

 

Prim算法与Dijkstra算法使用的思想几乎完全相同，只有在数组d[]的含义上有区别。（关于Dijkstra算法具体可以看前面写的《图的算法专题——最短路径》）

Dijkstra中d[]含义为起点s到达顶点Vi的最短距离，而Prim算法d[]含义为顶点Vi与集合S的最短距离，两者区别仅在于最短距离是到 起点 还是 集合 。

 

邻接矩阵版：

const int maxn=1000;
const int INF=1000000000;
int n,G[maxn][maxn];
int d[maxm]; //顶点到集合S的距离
bool vis[maxn]={ false};

int prim(){ //默认0号为初始点，函数返回最小生成树的边权之和
    fill(d,d+maxn,INF);
    d[0]=0;
    int ans=0; //边权之和
    for(int i=0;i){
        int u=-1,MIN=INF;
        for(int j=0;j){
            if(vis[j]==false&&d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return -1;
        vis[u]=true;
        ans+=d[u]; //将与集合S距离最小的边加入最小生成树
        for(int v=0;v){
            if(vis[v]==false && G[u][v]!=INF && G[u][v]<d[v] ){  
                d[v]=G[u][v]; //以u为中介点可以使v离集合S更近（u已被并入集合）
            }
        }
    }
    return ans;
}

 

 

邻接表版：

struct Node{
    int v,dis;  //v为目标顶点，dis为边权
};
vector Adj[maxn];
int n,d[maxn];
bool vis[maxn]={ false};
int prim(){
    fill(d,d+maxn,INF);
    d[0]=0;
    int ans=0;
    for(int i=0;i){
        int u=-1,MIN=INF;
        for(int j=0;j){
            if(vis[j]==false && d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return -1;
        vis[u]=true;
        ans+=d[u];
        for(int j=0;j){
            int v=Adj[u][j].v;
            if(vis[v]==false && Adj[u][j].dis< d[v]){
                d[v]=Adj[u][j].dis;
            }
        }
    }
    return ans;
}

 

2、Kruskal算法

算法流程：

（1）对所有边权从小到大排序。

（2）按边权从小到大测试所有边，如果当前测试边所连接的两个顶点不在同一个连通块中，则并入，否则舍弃。 （运用并查集）

（3）循环执行（2）直到最小生成树的边数等于总顶点数减1或是测试完所有边时结束。若结束时边数不为顶点数减1，则图不连通。

 

const int MAXV=110;
const int MAXE=10010;
int father[MAXV];
int findFather(int x){
    int a=x;
    while(x!=father[x]){
        x=father[x];
    }
    while(a!=father[a]){
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
struct edge{
    int u,v; //边的两个端点编号
    int cost; //边权
}E[MAXE];
bool cmp(edge a,edge b){
    return a.cost<b.cost;
}
int kruskal(int n,int m){  //n为顶点个数，m为图的边数
    int ans=0,Num_Edge=0;
    for(int i=1;i<=n;i++) father[i]=i; //假设顶点范围为1到n 
    sort(E,E+m,cmp);
    for(int i=0;i//枚举边
        int faU=findFather(E[i].u);
        int faV=findFather(E[i].v);
        if(faU!=faV){
            father[faU]=faV;
            ans+=E[i].cost;
            Num_Edge++;
            if(Num_Edge==n-1) break;
        }
    }
    if(Num_Edge != n-1) return -1;
    else return ans;
}