最小生成树(Kruskal算法和Prim算法)

最小生成树：

一个有n个结点的连通图的生成树，是原图的极小连通子图，包含原图放入所有结点，并且保持图连通的最小的边。求最小生成树可以用Kruskal(克鲁斯卡尔)算法和Prim(普里姆)算法求出。

Kruskal算法：

具体思路：是将每条边上的权进行排序，之后在从中选取最小的边，加入最小树的集合中。

注意：在以上的过程中得防止出现环路。可以用并查集维护。
以下图为例：

首先，建图，用一个结构体数组:

struct node{
int x;  //起点
int y;  //终点
int w;  //权重
}graph[100];

之后，用并查集判断是否会产生环路：

int point[100];  //用来标记结点
for(int i=1;i<=n;i++){
    point[i]=i;  //先将每个结点的根节点都设为自己
}

/*查找*/
int find(int n){
if(n==point[n]) return n;//返回结点的根节点
    find(point[n]);
}

/*合并*/
for(int i=1;i<=m;i++){
int fx = find(graph[i].x); //查找根节点
int fy = find(graph[i].y); //查找根节点
//若这条边的起点和终点相同，说明形成环路
if(fy!=fx){
        point[fy] = fx;  //不相等，则合并(纳入最小树的集合)
    }
}

完整代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; 
const int M =100;

int n; //结点数
int m; //边数
int point[M];  //并查集 

//图的结构体数组 
struct node{
int x;    //起点 
int y;    //终点 
int w;    //权重 
}graph[M];

//并查集：查找 
int find(int x){
if(point[x]==x) return x;
return find(point[x]);
}

int cmp(node a,node b){
return a.w<b.w;
}

int main(){
int sum;
while(cin>>n>>m){
for(int i=1;i<=n;i++){
            point[i] = i;
        }
// 建图 
for(int i=1;i<=m;i++){
cin>>graph[i].x>>graph[i].y>>graph[i].w; 
        }
// 按照边上的权重大小排序 
        sort(graph+1,graph+m+1,cmp);
        sum = 0;
for(int i=1;i<=m;i++){
int fx = find(graph[i].x); //集合的顶点 
int fy = find(graph[i].y); //集合的顶点 
//判断是否形成环路 
if(fy!=fx){
                sum+=graph[i].w;
                point[fy] = fx;  //纳入集合 
            }
        }
cout<<sum<<endl;  //输出最小连通图的权值的和
    }
return 0;
}

Prim算法

对于Prim算法,相对于Kruskal算法而言，Prim算法，适用于稠密图，即：边比较少的图。也就是说Kruskal算法比较适用于稀疏图。

具体思路：以图中的任意一个结点作为起点，逐个找到各个结点的最小权值的边(当前局部最小，达到整体最小)。来构建最小生成树。
首先，建图：

/*用一个二维数组cost[][]，建图*/
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x,y,len;
        cin>>x>>y>>len;
        cost[x][y] = len;
        cost[y][x] = len;
    }
}   

核心代码：

int Prim(int m){
int sum=0,k,min; 
for(int i=0;i<n;i++){
        dist[i] = cost[m][i];
    }
    dist[m]=0;
for(int i=1;i<n;i++){
        sum = 0,min = MAX;
for(int j=0;j<n;j++){
if(dist[j]&&dist[j]<min){
min = dist[j];
                 k = j;
            }
        }
        sum += min;
        dist[k] = 0;
for(int j=0;j<n;j++){
if(dist[j]&&dist[j]>cost[k][j]){
                dist[j] = cost[k][j];
            }
        }
    }
return sum;
}   

完整代码：

#include<iostream>
#include<cstring>
using namespace std;

const int M=100;
const int MAX = 1<<30;
int cost[M][M];
int dist[M]; //用来记录当前所在结点，到其他结点的边上的权值
int n; //结点数
int m; //边数
int  Prim(int m){
int i,j,k,min,sum = 0;
//初始化dist[]中的值，即：与m结点相连接的边上的权值
for(i=0;i<n;i++){
        dist[i] = cost[m][i];
    }
    dist[m] = 0; //标记
//第一个结点，不做处理
for(i=1;i<n;i++){
        min = MAX;
//找到dist[]中最小的值
for(j=0;j<n;j++){
if(dist[j]!=0&&dist[j]<min){
                min = dist[j];
                k = j;//记录下当前结点的位置
            }
        }
        sum +=min;
        dist[k] = 0;  //第k个结点取过了，标记为0
//更新dist[]，中的值，即：与k结点相连接的边的权值
for(j=0;j<n;j++){
if(dist[j]!=0&&dist[j]>cost[k][j]){
                dist[j] = cost[k][j];
            }
        }

    }
return sum; //返回最小连通图的边上的权值总和
} 

int main()
{
while(cin>>n>>m){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
                cost[i][j] = MAX;
            }
        }
for(int i=0;i<m;i++){
int x,y,len;
cin>>x>>y>>len;
            cost[x][y]=len;
            cost[y][x]=len;
        } 
//这里以v0为起点
cout<<Prim(0)<<endl;
    }
}