提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
贪心算法
贪心算法----定义：
使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边
- 贪心算法是计算图的最小生成树的基础算法，它的基本原理就是切分定理，
- 使用切分定理找到最小生成树的一条边，不断的重复直到找到最小生成树的所有边。
- 如果图有V个顶点，那么需要找到V-1条边，就可以表示该图的最小生成树。
贪心算法----原理:
最小生成树的算法
- 计算图的最小生成树的算法有很多种，但这些算法都可以看做是贪心算法的一种特殊情况，
- 这些算法的不同之处在于保存切分和判定权重最小的横切边的方式。
Prim算法
- 我们学习第一种计算最小生成树的方法叫Prim算法，它的每一步都会为一棵生成中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入到树中。
切分规则：
- 把最小生成树中的顶点看做是一个集合，把不在最小生成树中的顶点看做是另外一个集合。
算法API设计
Prim算法的实现原理
Prim算法始终将图中的顶点切分成两个集合，最小生成树顶点和非最小生成树顶点，通过不断的重复做某些操作，可以逐渐将非最小生成树中的顶点加入到最小生成树中，直到所有的顶点都加入到最小生成树中
- 我们在设计API的时候，使用最小索引优先队列存放树中顶点与非树中顶点的有效横切边，那么它是如何表示的呢？我们可以让最小索引优先队列的索引值表示图的顶点，让最小索引优先队列中的值表示从其他某个顶点到当前顶点的边权重。
1. 初始化状态
- 初始化状态，先默认0是最小生成树中的唯一顶点，其他的顶点都不在最小生成树中，此时横切边就是顶点0的邻接表中0-2,0-4,0-6,0-7这四条边，我们只需要将索引优先队列的2、4、6、7索引处分别存储这些边的权重值就可以表示了。
2. 找出权重最小的边,加入树中
现在只需要从这四条横切边中找出权重最小的边，然后把对应的顶点加进来即可。所以找到0-7这条横切边的权重最小，因此把0-7这条边添加进来，此时0和7属于最小生成树的顶点，其他的不属于，现在顶点7的邻接表中的边也成为了横切边，
这时需要做两个操作：
- 0-7这条边已经不是横切边了，需要让它失效：只需要调用最小索引优先队列的delMin()方法即可完成；
-
2和4顶点各有两条连接指向最小生成树，需要只保留一条：
4-7的权重小于0-4的权重，所以保留4-7，调用索引优先队列的change(4,0.37)即可，
0-2的权重小于2-7的权重，所以保留0-2，不需要做额外操作。
3.重复上面的动作，
- 我们不断重复上面的动作，就可以把所有的顶点添加到最小生成树中。
辅助类
1.Edge—边
package graph.tu;
public class Edge implements Comparable<Edge> {
private final int v;//顶点一
private final int w;//顶点二
private final double weight;//当前边的权重
//通过顶点v和w，以及权重weight值构造一个边对象
public Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
//获取边的权重值
public double weight(){
return weight;
}
//获取边上的一个点
public int either(){
return v;
}
//获取边上除了顶点vertex外的另外一个顶点
public int other(int vertex){
if (vertex==v){
return w;
}else{
return v;
}
}
@Override
public int compareTo(Edge that) {
//使用一个遍历记录比较的结果
int cmp;
if (this.weight()>that.weight()){
//如果当前边的权重值大，则让cmp=1；
cmp = 1;
}else if (this.weight()<that.weight()){
//如果当前边的权重值小，则让cmp=-1；
cmp=-1;
}else{
//如果当前边的权重值和that边的权重值一样大，则让cmp=0
cmp = 0;
}
return cmp;
}
}
2.EdgeWeightedGraph—加权无向图
package graph.tu;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class EdgeWeightedGraph {
//顶点总数
private final int V;
//边的总数
private int E;
//邻接表
private Queue<Edge>[] adj;
//创建一个含有V个顶点的空加权无向图
public EdgeWeightedGraph(int v) {
//初始化顶点数量
this.V = v;
//初始化边的数量
this.E = 0;
//初始化邻接表
this.adj = new ConcurrentLinkedQueue[v];
for (int i = 0; i < adj.length; i++) {
adj[i] = new ConcurrentLinkedQueue<Edge>();
}
}
//获取图中顶点的数量
public int V() {
return V;
}
//获取图中边的数量
public int E() {
return E;
}
//向加权无向图中添加一条边e
public void addEdge(Edge e) {
//需要让边e同时出现在e这个边的两个顶点的邻接表中
int v = e.either();
int w = e.other(v);
adj[v].offer(e);
adj[w].offer(e);
//边的数量+1
E++;
}
//获取和顶点v关联的所有边
public Queue<Edge> adj(int v) {
return adj[v];
}
//获取加权无向图的所有边
public Queue<Edge> edges() {
//创建一个队列对象，存储所有的边
Queue<Edge> allEdges = new ConcurrentLinkedQueue<>();
//遍历图中的每一个顶点，找到该顶点的邻接表，邻接表中存储了该顶点关联的每一条边
//因为这是无向图，所以同一条边同时出现在了它关联的两个顶点的邻接表中，需要让一条边只记录一次；
for(int v =0;v<V;v++){
//遍历v顶点的邻接表，找到每一条和v关联的边
for (Edge e : adj(v)) {
if (e.other(v)<v){
allEdges.offer(e);
}
}
}
return allEdges;
}
}
3.IndexMinPriorityQueue----最小优先队列
package graph.tu;
public class IndexMinPriorityQueue<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//保存每个元素在items数组中的索引，pq数组需要堆有序
private int[] pq;
//保存qp的逆序，pq的值作为索引，pq的索引作为值
private int[] qp;
//记录堆中元素的个数
private int N;
public IndexMinPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity+1];
this.pq = new int[capacity+1];
this.qp= new int[capacity+1];
this.N = 0;
//默认情况下，队列中没有存储任何数据，让qp中的元素都为-1；
for (int i = 0; i < qp.length; i++) {
qp[i]=-1;
}
}
//获取队列中元素的个数
public int size() {
return N;
}
//判断队列是否为空
public boolean isEmpty() {
return N==0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i, int j) {
return items[pq[i]].compareTo(items[pq[j]])<0;
}
//交换堆中i索引和j索引处的值
private void exch(int i, int j) {
//交换pq中的数据
int tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
//更新qp中的数据
qp[pq[i]]=i;
qp[pq[j]] =j;
}
//判断k对应的元素是否存在
public boolean contains(int k) {
return qp[k] !=-1;
}
//最小元素关联的索引
public int minIndex() {
return pq[1];
}
//往队列中插入一个元素,并关联索引i
public void insert(int i, T t) {
//判断i是否已经被关联，如果已经被关联，则不让插入
if (contains(i)){
return;
}
//元素个数+1
N++;
//把数据存储到items对应的i位置处
items[i] = t;
//把i存储到pq中
pq[N] = i;
//通过qp来记录pq中的i
qp[i]=N;
//通过堆上浮完成堆的调整
swim(N);
}
//删除队列中最小的元素,并返回该元素关联的索引
public int delMin() {
//获取最小元素关联的索引
int minIndex = pq[1];
//交换pq中索引1处和最大索引处的元素
exch(1,N);
//删除qp中对应的内容
qp[pq[N]] = -1;
//删除pq最大索引处的内容
pq[N]=-1;
//删除items中对应的内容
items[minIndex] = null;
//元素个数-1
N--;
//下沉调整
sink(1);
return minIndex;
}
//删除索引i关联的元素
public void delete(int i) {
//找到i在pq中的索引
int k = qp[i];
//交换pq中索引k处的值和索引N处的值
exch(k,N);
//删除qp中的内容
qp[pq[N]] = -1;
//删除pq中的内容
pq[N]=-1;
//删除items中的内容
items[k]=null;
//元素的数量-1
N--;
//堆的调整
sink(k);
swim(k);
}
//把与索引i关联的元素修改为为t
public void changeItem(int i, T t) {
//修改items数组中i位置的元素为t
items[i] = t;
//找到i在pq中出现的位置
int k = qp[i];
//堆调整
sink(k);
swim(k);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k) {
while(k>1){
if (less(k,k/2)){
exch(k,k/2);
}
k = k/2;
}
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k) {
while(2*k<=N){
//找到子结点中的较小值
int min;
if (2*k+1<=N){
if (less(2*k,2*k+1)){
min = 2*k;
}else{
min = 2*k+1;
}
}else{
min = 2*k;
}
//比较当前结点和较小值
if (less(k,min)){
break;
}
exch(k,min);
k = min;
}
}
}
Prim算法----PrimMST
package graph.tu;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
public class PrimMST {
//索引代表顶点，值表示当前顶点和最小生成树之间的最短边
private Edge[] edgeTo;
//索引代表顶点，值表示当前顶点和最小生成树之间的最短边的权重
private double[] distTo;
//索引代表顶点，如果当前顶点已经在树中，则值为true，否则为false
private boolean[] marked;
//存放树中顶点与非树中顶点之间的有效横切边
private IndexMinPriorityQueue<Double> pq;
//根据一副加权无向图，创建最小生成树计算对象
public PrimMST(EdgeWeightedGraph G) {
//初始化edgeTo
this.edgeTo = new Edge[G.V()];
//初始化distTo
this.distTo = new double[G.V()];
for (int i = 0; i < distTo.length; i++) {
distTo[i] = Double.POSITIVE_INFINITY;
}
//初始化marked
this.marked = new boolean[G.V()];
//初始化pq
pq = new IndexMinPriorityQueue<Double>(G.V());
//默认让顶点0进入到树中，但是树中只有一个顶点0，因此，0顶点默认没有和其他的顶点相连，所以让distTo对应位置处的值存储0.0
distTo[0] = 0.0;
pq.insert(0,0.0);
//遍历索引最小优先队列，拿到最小和N切边对应的顶点，把该顶点加入到最小生成树中
while (!pq.isEmpty()){
visit(G,pq.delMin());
}
}
//将顶点v添加到最小生成树中，并且更新数据
private void visit(EdgeWeightedGraph G, int v) {
//把顶点v添加到最小生成树中
marked[v] = true;
//更新数据
for (Edge e : G.adj(v)) {
//获取e边的另外一个顶点(当前顶点是v)
int w = e.other(v);
//判断另外一个顶点是不是已经在树中，如果在树中，则不做任何处理，如果不再树中，更新数据
if (marked[w]){
continue;
}
//判断边e的权重是否小于从w顶点到树中已经存在的最小边的权重；
if (e.weight()<distTo[w]){
//更新数据
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w)){
pq.changeItem(w,e.weight());
}else{
pq.insert(w,e.weight());
}
}
}
}
//获取最小生成树的所有边
public Queue<Edge> edges() {
//创建队列对象
Queue<Edge> allEdges = new ConcurrentLinkedQueue<>();
//遍历edgeTo数组，拿到每一条边，如果不为null，则添加到队列中
for (int i = 0; i < edgeTo.length; i++) {
if (edgeTo[i]!=null){
allEdges.offer(edgeTo[i]);
}
}
return allEdges;
}
}
测试类
package graph.tu;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
public class PrimMSTTest {
public static void main(String[] args) throws Exception{
//准备一副加权无向图
BufferedReader br = new BufferedReader(new InputStreamReader(PrimMSTTest.class.getClassLoader().getResourceAsStream("main/resources/min_create_tree_test.txt")));
int total = Integer.parseInt(br.readLine());
graph.tu.EdgeWeightedGraph G = new graph.tu.EdgeWeightedGraph(total);
int edgeNumbers = Integer.parseInt(br.readLine());
for (int e = 1;e<=edgeNumbers;e++){
String line = br.readLine();//4 5 0.35
String[] strs = line.split(" ");
int v = Integer.parseInt(strs[0]);
int w = Integer.parseInt(strs[1]);
double weight = Double.parseDouble(strs[2]);
//构建加权无向边
Edge edge = new Edge(v, w, weight);
G.addEdge(edge);
}
//创建一个PrimMST对象，计算加权无向图中的最小生成树
graph.tu.PrimMST primMST = new graph.tu.PrimMST(G);
//获取最小生成树中的所有边
Queue<Edge> edges = primMST.edges();
//遍历打印所有的边
for (Edge e : edges) {
int v = e.either();
int w = e.other(v);
double weight = e.weight();
System.out.println(v+"-"+w+" :: "+weight);
}
}
}
kruskal算法
主要思想:
按照边的权重(从小到大)处理它们，将边加入最小生成树中
- kruskal算法是计算一副加权无向图的最小生成树的另外一种算法，它的主要思想是按照边的权重(从小到大)处理它们，将边加入最小生成树中，加入的边不会与已经加入最小生成树的边构成环，直到树中含有V-1条边为止。
kruskal算法和prim算法的区别：
- Prim算法是一条边一条边的构造最小生成树，每一步都为一棵树添加一条边。
- kruskal算法构造最小生成树的时候也是一条边一条边地构造，但它的切分规则是不一样的。它每一次寻找的边会连接一片森林中的两棵树。如果一副加权无向图由V个顶点组成，初始化情况下每个顶点都构成一棵独立的树，则V个顶点对应V棵树，组成一片森林，kruskal算法每一次处理都会将两棵树合并为一棵树，直到整个森林中只剩一棵树为止。
API设计
kruskal算法的实现原理
- 在设计API的时候，使用了一个MinPriorityQueue pq存储图中所有的边，每次使用pq.delMin()取出权重最小的边，并得到该边关联的两个顶点v和w，通过uf.connect(v,w)判断v和w是否已经连通，如果连通，则证明这两个顶点在同一棵树中，那么就不能再把这条边添加到最小生成树中，因为在一棵树的任意两个顶点上添加一条边，都会形成环，而最小生成树不能有环的存在，如果不连通，则通过uf.connect(v,w)把顶点v所在的树和顶点w所在的树合并成一棵树，并把这条边加入到mst队列中，这样如果把所有的边处理完，最终mst中存储的就是最小生树的所有边。
辅助类
1.Edge—边
2.EdgeWeightedGraph—加权无向图
3.UF_Tree_Weighted—并查集
package graph.tu;
public class UF_Tree_Weighted {
//记录结点元素和该元素所在分组的标识
private int[] eleAndGroup;
//记录并查集中数据的分组个数
private int count;
//用来存储每一个根结点对应的树中保存的结点的个数
private int[] sz;
//初始化并查集
public UF_Tree_Weighted(int N){
//初始化分组的数量,默认情况下，有N个分组
this.count = N;
//初始化eleAndGroup数组
this.eleAndGroup = new int[N];
//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素，并且让每个索引处的值(该元素所在的组的标识符)就是该索引
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
this.sz = new int[N];
//默认情况下，sz中每个索引处的值都是1
for (int i = 0; i < sz.length; i++) {
sz[i] = 1;
}
}
//获取当前并查集中的数据有多少个分组
public int count(){
return count;
}
//判断并查集中元素p和元素q是否在同一分组中
public boolean connected(int p,int q){
return find(p) == find(q);
}
//元素p所在分组的标识符
public int find(int p){
while(true){
if (p == eleAndGroup[p]){
return p;
}
p = eleAndGroup[p];
}
}
//把p元素所在分组和q元素所在分组合并
public void union(int p,int q){
//找到p元素和q元素所在组对应的树的根结点
int pRoot = find(p);
int qRoot = find(q);
//如果p和q已经在同一分组，则不需要合并了
if (pRoot==qRoot){
return;
}
//判断proot对应的树大还是qroot对应的树大，最终需要把较小的树合并到较大的树中
if (sz[pRoot]<sz[qRoot]){
eleAndGroup[pRoot] = qRoot;
sz[qRoot]+=sz[pRoot];
}else{
eleAndGroup[qRoot] = pRoot;
sz[pRoot]+= sz[qRoot];
}
//组的数量-1
this.count--;
}
}
kruskal算法----KruskalMST
- PriorityQueue—java.util
package graph.tu;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedDeque;
public class KruskalMST {
//保存最小生成树的所有边
private Queue<Edge> mst;
//索引代表顶点，使用uf.connect(v,w)可以判断顶点v和顶点w是否在同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并
private UF_Tree_Weighted uf;
//存储图中所有的边，使用最小优先队列，对边按照权重进行排序
private Queue<Edge> pq;
//根据一副加权无向图，创建最小生成树计算对象
public KruskalMST(EdgeWeightedGraph G) {
//初始化mst
this.mst = new ConcurrentLinkedDeque<>();
//初始化uf
this.uf = new UF_Tree_Weighted(G.V());
//初始化pq
this.pq = new PriorityQueue<>(G.E()+1);
//把图中所有的边存储到pq中
for (Edge e : G.edges()) {
pq.offer(e);
}
//遍历pq队列，拿到最小权重的边，进行处理
while(!pq.isEmpty() && mst.size()<G.V()-1){
//找到权重最小的边
Edge e = pq.poll();
//找到该边的两个顶点
int v = e.either();
int w = e.other(v);
//判断这两个顶点是否已经在同一颗树中，如果在同一颗树中，则不对该边做处理，如果不在一棵树中，则让这两个顶点属于的两棵树合并成一棵树
if (uf.connected(v,w)){
continue;
}
uf.union(v,w);
//让边e进入到mst队列中
mst.offer(e);
}
}
//获取最小生成树的所有边
public Queue<Edge> edges() {
return mst;
}
}