最小生成树（MST）基本概念
生成树是一种依托在加权图上的概念，而加权图是一种为每条边关联一个权值或者是成本的图模型。
最小生成树：给定一副加权无向图，找到它的一颗最小生成树。图的生成树是它的一颗含有其所有顶点的无环连通子图。一副加权图的最少小生成树（MST）是树中所有边的权值之和最小的生成树。
最小生成树的前提条件是树的两个重要性质：
用一条边连接树的任意两个顶点都会产生一个新的环。
从树中删去一条边将会得到两颗独立的树。
切分定理：图的一种切分是将图的所有顶点切分成两个非空且不重合的集合。横切边是一条链接两个属于不同集合顶点的边。在一副加权图中，给定任意的切分，它的横切边中权重最小者必然属于最小生成树。
要找到最小生成树，需要是要到贪心算法，即使用切分定理找到最小生成树的最小边，不断重复，每次都找最小边，直到找到最小生成树所有边。
数据结构实现
要实现最小生成树，首先要需要有一个定义加权图的边类，并且要实现Comparable，用来排序，找到权重最小的那条边
/**
* 加权图的边
*/
public class Edge implements Comparable<Edge>{
private final int v;//顶点1
private final int w;//顶点2
private final double weight;//权重
public Edge(int v,int w,double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public int getV() {
return v;
}
public int getW() {
return w;
}
/**
*获取边的权重
/
public double getWeight() {
return weight;
}
/**
* 返回另一个顶点
* @param vertex
* @return
*/
public int other(int vertex){
if(vertex == v)return w;
if(vertex == w)return v;
else throw new RuntimeException("没有该顶点");
}
/**
* 用来排序比较
*/
@Override
public int compareTo(Edge e) {
if(this.weight < e.getWeight()) return -1;
else if(this.weight > e.getWeight()) return 1;
else return 0;
}
}加权图主要从文件中获取数据
/**
* 加权图
* @author yuli
*
*/
public class EdgeWeightedGraph {
private final int v;//顶点数
private int e;//边数
private List<Edge>[] adj;//邻接表
@SuppressWarnings("unchecked")
public EdgeWeightedGraph(int v,int e) {
this.v = v;
adj = new LinkedList[v];
for(int i=0;i<v;i++){
adj[i] = new LinkedList<Edge>();
}
}
@SuppressWarnings("unchecked")
public EdgeWeightedGraph(File file) throws IOException{
FileReader fr = new FileReader(file);
BufferedReader br = new BufferedReader(fr);
int vertex = Integer.parseInt(br.readLine());//读取顶点数
this.v = vertex;//读取顶点数
//创建有顶点数的邻接表
adj = new LinkedList[vertex];
for(int i=0;i<vertex;i++){
adj[i] = new LinkedList<>();
}
int edge = Integer.parseInt(br.readLine());//读取边
for(int i=0;i<edge;i++){
//获取顶点对
String[] vertexs = br.readLine().split(" ");
int v = Integer.parseInt(vertexs[0]);
int m = Integer.parseInt(vertexs[1]);
double weight = Double.parseDouble(vertexs[2]);
//生成加权边
Edge e = new Edge(v, m, weight);
//将顶点对添加成一条边
addEdge(v, m,e);
}
if(br!= null){
br.close();
}
}
/**
* 获取边数
* @return
*/
public int getE() {
return e;
}
/**
* 获取顶点数
* @return
*/
public int getV() {
return v;
}
/**
* 添加一条无相边
* @param v
* @param m
* @param e
*/
private void addEdge(int v,int m,Edge e){
adj[v].add(e);
adj[m].add(e);
this.e++;
}
/**
* 获取邻接点
* @param v
* @return
*/
public Iterable<Edge> adj(int v){
return adj[v];
}
/**
* 获取所有边
* @return
*/
public Iterable<Edge> edges(){
List<Edge> edges = new ArrayList<>();
for (List<Edge> list : adj) {
edges.addAll(list);
}
return edges;
}
}