最小生成树算法模板 Java实现

• 问题描述
• Prim算法
• Kruskal算法

在一个带权连通图图中找出一颗最小生成树，求其权值之和。

public class Prim {
	public static int inf=65535;
	public static int minval=0;
	
	public static void prim(int [][]map,int n) {
		int min,i,j,k;
		int visit[]=new int[n];//0表示未选择 ；1表示已选择
		int lowcost[]=new int[n];//表示顶点i到已选择的顶点集中的最短边的权值  若i在顶点集中，则为inf
		//首先选择点0
		lowcost[0]=inf;
		visit[0]=1;
		for(i=1;i 
时间复杂度:
      
       
        
         
          O
         
         
          (
         
         
          
           n
          
          
           2
          
         
         
          )
         
        
        
         O(n^{2})
        
       
      O(n2)
可使用二叉堆优化为:
      
       
        
         
          O
         
         
          (
         
         
          e
         
         
          l
         
         
          o
         
         
          
           g
          
          
           2
          
         
         
          n
         
         
          )
         
        
        
         O(elog_2n)
        
       
      O(elog2​n)
适用于稠密图
 
Kruskal算法 
import java.util.*;
class Edge{
	int begin;
	int end;
	int weight;
	public int getWeight()
	{
		return weight;
	}
}
public class Kruskal {
	public static int inf=65535;
	public static int minval=0;
	public static void kruskal(int map[][]) {
		int i,j,m,n;
		int parent[]=new int[map.length];
		//读入所有边，并按权值从小到大排序
		Listedges=new ArrayList();//定义边集数组
		for(i=0;i 
时间复杂度:
      
       
        
         
          O
         
         
          (
         
         
          e
         
         
          
           
            log
           
           
            ⁡
           
          
          
           2
          
         
         
          e
         
         
          )
         
        
        
         O(elog_2e)
        
       
      O(elog2​e)
适用于稀疏图（边少）
 
 
 
参考资料：《大话数据结构》