1.Prim算法 

时间是复杂度O（n2），适合稠密图。 

例：Poj–1258 

题目大意：n个城市建造光缆，要使这些城市直接通信，并且光缆费用最小。 



#include <cstdio>
#include <string.h>
#define n 10010
#define inf 100010
int a[n][n],ans;
bool vis[n],t;
int dis[n];
bool prim()
{
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=t; i++)
        dis[i]=inf;
    ans=0;
    dis[1]=0;
    for(int i=1; i<=t; i++)
    {
        int temp=inf,k=0;
        for(int j=1; j<=t; j++)
        {
            if((vis[j]==0)&&(dis[j]<temp))
            {
                temp =dis[j];
                k=j;
            }
        }
        if(temp==n)
            return false;
        vis[k]=true;
        ans+=temp;
        for(int j=1; j<=t; j++)
        {
            if(vis[j]==0&&dis[j]>a[k][j])
                dis[j]=a[k][j];
        }
    }
    return true;
}
int main()
{
    while(~scanf("%d",&t))
    {
        ans=0;
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                scanf("%d",&a[i][j]);
        prim();
        printf("%d\n",ans);
    }
    return 0;
}

2.Kruskal算法 

时间复杂度O（elog2e），适合简单图。 

例如：Poj–2485 

题目大意：给定一些地点和连通它们的可以修的公路，每条路有不同长度，求修建一些路使它们连通，并且所有路长度最小。    



#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1001
#define inf 1000000001
#define M N*N
int t;
int e,n,m;
int f[N];
struct note
{
    int u,v;
    int c;
    note() {}
    note(int u,int v,int c):u(u),v(v),c(c) {}
} p[M];
void add(int u,int v,int c)
{
    p[e++]=note (u,v,c);
}
int cmp(const void * a,const void * b)
{
    note *aa=(note *)a;
    note *bb=(note *)b;
    return aa->c-bb->c;
}
void made()
{
    int i;
    for(i=0; i<=n; i++)
        f[i]=i;
}
int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
int  kru(int n)
{
    qsort(p,e,sizeof(p[0]),cmp);
     made();
    int m=0,ans=0;
    int i,j;
    for(i=0; i<e; i++)
    {
        int xx=find(p[i].u);
        int yy=find(p[i].v);
        if(xx==yy)
            continue;
        m++;
        ans =p[i].c;
        f[yy]=xx;
        if(m==n-1)
            break;
    }
    if(m<n-1)
        return -1;
    else return ans;
}
int main()
{
    int i,j,l,c;;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        e=0;
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                scanf("%d",&c);
                add(i,j,c);
            }
        printf("%d\n",kru(n));
    }
    return 0;
}

最小生成树算法总结

Kruskal算法

Kruskal算法是典型的最小生成树算法，用于计算将所有顶点连通的最小权值。

最常见的问题就是：已知N座城市中任意两座城市之间建造道路所需要的费用，求最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达。

算法核心：首先选择最短的边，然后选择次短的边……直到选择n-1条边为止。算法的时间复杂度为O(MlogM)，空间复杂度为O(M)。

基本步骤如下：

对所有的边按照权值进行从小到大排序。
	
然后每次选取最小的权值，如果和已有点集构成环则跳过，否则加到该点集中，直到选择了n-1条边让整个图连通为止。最终由所有的点集构成的树就是最佳的。
Kruskal算法核心代码：

for (i = 1; i <= m; i++) {//开始从小到大枚举每一条边
    //判断一条边的两个顶点是否连通，即判断是否已在同一个集合中
    if (merge(e[i].u, e[i].v)) {//如果目前尚未不连通，则选用这条边
        counts++;
        sum += e[i].w;
    }
    if (counts == n - 1) //直到选用了n-1条边之后退出循环
        break;
}

Prim算法

Prim算法是主要解决与边数无关和顶点树有关的算法，适合求解稠密网的最小生成树。

最常见的问题就是：已知N座城市中任意两座城市之间建造道路所需要的费用，求最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达。

算法核心：每在最小生成树集合中加入一个点就需要把这个点与集合外的点比较，不断的寻找两个集合之间最小的边。

算法的时间复杂度为O(N2)，空间复杂度为O(N2)。

基本步骤如下：

从任意个顶点开始构造生成树，假设就从1号顶点吧。首先将顶点1加入生成树中，用一个一维数组book来标记哪些顶点已经加入了生成树。
	
用数组dis记录生成树到各个顶点的距离。最初生成树中只有1号顶点，有直连边时，数组dis中存储的就是1号顶点到该顶点的边的权值，没有直连边的时候就是无穷大，即初始化dis数组。
	
从数组dis中选出离生成树最近的顶点(假设这个顶点为j)加入到生成树中(即在数组dis中找最小值)。再以j为中间点，更新生成树到每一个非树顶点的距离(就是松弛啦)，即如果dis[k]>e[j][k]则更新dis[k]=e[j][k]。
	
重复第3步，直到生成树中有n个顶点为止。
Prim算法核心代码：

//将1号顶点加入生成树
book[1] = 1; //这里用book来标记一个顶点是否已经加入生成树
count++;
while (count < n) {
    min = inf;
    for (i = 1; i <= n; i++) {
        if (!book[i] && dis[i] < min) {
            min = dis[i];
            j = i;
        }
    }
    book[j] = 1;
    count++;
    sum += dis[j];
    //扫描当前顶点j的所有的边，再以j为中间点，更新生成树到每一个非树顶点的距离
    for (k = 1; k <= n; k++) {
        if (!book[k] && dis[k] > e[j][k])
            dis[k] = e[j][k];
    }
}

利用prim算法实现的最小生成树算法

将集合U划分为A和B两个子集，不断的将连接A，B集合的最小权值的点不断的从B中加入到A中，直到遍历整个集合U。

算法过程：

先选取一个初始点作为集合A，集合B为ADev补集
选取连接集合A，B的权值最小边，将在集合B中的点添加到集合A中
不断的重复上面的过程

算法复杂度O（n*n）

import java.util.Arrays;

class Graph{
	char[] vexs;
	int[][] edges;
	
	public static final int INF=Integer.MAX_VALUE;
	
	
	public Graph(char[] vexs,int[][] edges) {
		this.edges=edges;
		this.vexs=vexs;
	}
	
	public void prim(int start) {
		if(start<0)
			return;
		int len=vexs.length;
		int[] weights=new int[len];
		char[] prims=new char[len];
		int index=0;
		prims[index++]=vexs[start];
		for(int i=0;i<len;i++)
			weights[i]=edges[start][i];
		
		for(int i=0;i<len;i++){
			if(i==start)
				continue;
			int min=Integer.MAX_VALUE;
			int minINdex = 0;
			for(int j=0;j<len;j++){
				if(weights[j]!=0&&min>weights[j]){
					min=weights[j];
					minINdex=j;
				}
			}
			prims[index++]=vexs[minINdex];
			weights[minINdex]=0;
			for(int j=0;j<len;j++){
				if(weights[j]!=0&&weights[j]>edges[minINdex][j])
					weights[j]=edges[minINdex][j];
			}
		}
		
		int sum=0;
		for(int i=0;i<len-1;i++){
			int iIndexA=getPosition(prims[i]);
			int iIndexB=getPosition(prims[i+1]);
			sum+=edges[iIndexA][iIndexB];
		}
		//System.out.println(sum);
		System.out.println(Arrays.toString(prims));
	}

	private int getPosition(char c) {
		for(int i=0;i<vexs.length;i++)
			if(vexs[i]==c)
				return i;
		return -1;
	}
	
}

public class PrimMethod {

	private static final int INF = Integer.MAX_VALUE;

	public static void main(String[] args) {
		 char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
	        int edges[][] = {
	                 /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
	          /*A*/ {   0,  12, INF, INF, INF,  16,  14},
	          /*B*/ {  12,   0,  10, INF, INF,   7, INF},
	          /*C*/ { INF,  10,   0,   3,   5,   6, INF},
	          /*D*/ { INF, INF,   3,   0,   4, INF, INF},
	          /*E*/ { INF, INF,   5,   4,   0,   2,   8},
	          /*F*/ {  16,   7,   6, INF,   2,   0,   9},
	          /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
		Graph graph=new Graph(vexs, edges);
		graph.prim(0);
	}
	
}

kruskal算法

算法描述：先将边的权值进行排序，然后将边权从小到大依次操作，判断即将加入的边是否会在树中生成环，将不能生成环的加入到最小生成树中，否则舍弃这条边。

算法复杂度O（elge）e为边的个数
class Edge{
	int  start;
	int end;
	int value;
	
	public Edge(int start,int end,int value) {
		this.end=end;
		this.start=start;
		this.value=value;
	}
	
}

class Graph1{
	char[] vexs;
	int[][] edges;
	public Graph1(char[] vexs, int[][] edges) {
		super();
		this.vexs = vexs;
		this.edges = edges;
	
	}
	int edgeNum;
	private static final int INF=Integer.MAX_VALUE;
	public void kruskal() {
		//System.out.println(Arrays.toString(vexs));
		for(int i=0;i<vexs.length;i++)
			for(int j=i+1;j<vexs.length;j++)
				if(this.edges[i][j]!=INF)
					edgeNum++;
		
		
		Edge[] edges=buildEdge(this.edges,edgeNum);
		//System.out.println(Arrays.toString(this.edges));
		sortEdge(edges,0,edges.length-1);
		//System.out.println(Arrays.toString(edges));
		Edge[] resEdge=new Edge[edgeNum];
		int index=0;
		int[] edgeRelation=new int[edgeNum];
		for(int i=0;i<edges.length;i++){
			int end1=getEnd(edges[i].start,edgeRelation);
			int end2=getEnd(edges[i].end,edgeRelation);
			if(end1!=end2){
				resEdge[index++]=edges[i];
				edgeRelation[end1]=end2;
			}
		}
		for(int i=0;i<resEdge.length;i++)
			if(resEdge[i]!=null)
			System.out.println(vexs[resEdge[i].start]+"     end="+vexs[resEdge[i].end]);
	}
	
	

	private void sortEdge(Edge[] edges2,int start,int end) {
		if(start>=end)
			return;
		int mid=(end-start)/2;
		sortEdge(edges2, start,start+mid );
		sortEdge(edges2, start+mid+1, end);
		merge(edges2,start,start+mid+1,end);
	}

	private void merge(Edge[] edges2, int start,int mid,int end) {
		int tmp=mid,index=0,s=start;
		Edge[] data=new Edge[end-start+1];
		while(start<mid&&tmp<=end){
			if(edges2[start].value<=edges2[tmp].value){
				data[index++]=edges2[start];
				start++;
			}else{
				data[index++]=edges2[tmp];
				tmp++;
			}
		}
		while(start<mid){
			data[index++]=edges2[start];
			start++;
		}
		while(tmp<=end){
			data[index++]=edges2[tmp];
			tmp++;
		}
		for(int i=0;i<data.length;i++)
			edges2[s+i]=data[i];
	}

	private int getEnd(int end, int[] edgeRelation) {
		while(edgeRelation[end]!=0)
			end=edgeRelation[end];
		return end;
	}

	private Edge[] buildEdge(int[][] edges2, int length) {
		Edge[] edges=new Edge[length];
		int index=0,len=edges2.length;
		for(int i=0;i<len;i++)
			for(int j=i+1;j<len;j++)
				if(edges2[i][j]!=Integer.MAX_VALUE)
					edges[index++]=new Edge(i,j , edges2[i][j]);
		return edges;
	}
}

public class KruskalMethod {

	private static final int INF=Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int edges[][] = {
                 /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
          /*A*/ {   0,  12, INF, INF, INF,  16,  14},
          /*B*/ {  12,   0,  10, INF, INF,   7, INF},
          /*C*/ { INF,  10,   0,   3,   5,   6, INF},
          /*D*/ { INF, INF,   3,   0,   4, INF, INF},
          /*E*/ { INF, INF,   5,   4,   0,   2,   8},
          /*F*/ {  16,   7,   6, INF,   2,   0,   9},
          /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
		Graph1 graph=new Graph1(vexs, edges);
		graph.kruskal();
	}
	
}

目录
最小生成树算法
prim
kruskal

最小生成树算法
prim
时间复杂度： O(Elog2V)
适用范围： 稠密图
基本思路： 将任一点作为起点，将其所连接的最近的点加入，再从两点所连的点中找到最近的一个加入，依次类推。
模板：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define inf 0x3f3f3f3f
#define maxn 110

struct edge {
	int to;
	int dis;
	edge(int to, int dis) : to(to), dis(dis) {}
	bool operator < (const edge& b)const {
		return dis > b.dis;
	}
};

vector<edge> G[maxn];
bool vis[maxn];

void prim(int n) {
	int sum = 0;
	priority_queue<edge> pq;
	pq.push(edge(1, 0));
	while (!pq.empty()) {
		edge e = pq.top();
		pq.pop();
		if (vis[e.to]) {
			continue;
		}
		vis[e.to] = true;
		for (int i = 0; i < G[e.to].size(); ++i) {
			if(!vis[G[e.to][i].to]){
				pq.push(G[e.to][i]);
			}
		}
		sum += e.dis;
	}
	printf("%d\n", sum);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	int u, v, w;
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back(edge(v, w));
		G[v].push_back(edge(u, w));
	}
	prim(n);
	return 0;
}

kruskal
时间复杂度： O(Elog2E + E)
适用范围： 稀疏图
基本思路： 将边从小到大排好序，若边的两端点不再同一集中（连接不成圈），则将该边加入生成树中。
模板：
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

#define inf 0x3f3f3f3f
#define maxm 10010
#define maxn 2010

struct node {
	int from, to;
	int dis;
	node() {}
	node(int from, int to, int dis) : from(from), to(to), dis(dis) {}
	bool operator < (const node& b)const {
		return dis < b.dis;
	}
}edge[maxm];

int s[maxn];

int find(int u) {
	return s[u] == u ? u : find(s[u]);
}

void kruskal(int n, int m) {
	for (int i = 1; i <= n; ++i) {
		s[i] = i;
	}
	sort(edge, edge + m);
	int sum = 0;
	for (int i = 0; i < m; ++i) {
		int a = find(edge[i].from);
		int b = find(edge[i].to);
		if (a == b) {
			continue;
		}
		s[a] = b;
		sum += edge[i].dis;
	}
	printf("%d\n", sum);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	int u, v, w;
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		edge[i] = node(u, v, w);
	}
	kruskal(n, m);
	return 0;
}