武侠： 飞雪连天射白鹿，笑书神侠倚碧鸳。 ——金庸十四著作
飞狐外传 、雪山飞狐 、连城诀 、天龙八部 、射雕英雄传 、白马啸西风 、鹿鼎记 、笑傲江湖 、书剑恩仇录 、神雕侠侣 、侠客岛 、倚天屠龙记 、碧血剑 、鸳鸯刀 （除此之外还缺少越女剑）。
声明:本文参考了华山大师兄博客。结合自己学习《算法导论》的认识形成的笔记。感谢网友的总结分享。
1. 最小生成树的生成
一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树。Kruskal算法 和 Prim算法都是使用贪心策略来解决最小生成树的问题。
//无相连通图G(V,E)和权重函数w:E->R.Generic-MST(G,w){ A=Φ;//Φ表示空集 while(A does not from a spinning tree){ find a edge(u,v) that is safe for A; A=A∪{(u,v)} } return A;} 2. 克鲁斯卡尔算法
算法思想：遍历根据权重从小到大排序的边，依据约束，合并森林成为目标树。（自己理解的大白话）
1).记Graph中有v个顶点，e个边。 2).新建图Graphnew，Graphnew中拥有原图中相同的v个顶点，但没有边。 3).将原图Graph中所有e个边按权值从小到大排序 4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中 if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中 添加这条边到图Graphnew中3. 普里姆算法
算法思想：从一点出发，先添加连通的最近的结点，一直到所有的几点都包含在目标树中。（自己理解的大白话）
1).输入：一个加权连通图，其中顶点集合为V，边集合为E； 2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空； 3).重复下列操作，直到Vnew = V： a.在集合E中选取权值最小的边4. 算法Java实现**
4.1 图的存储和表示
package lbz.ch23.mst;import java.util.ArrayList;import java.util.Collections;import java.util.List;/** * @author LbZhang * @version 创建时间：2016年3月16日 下午9:11:24 * @description 图 */public class Graph { public final static int NODECOUNT = 9; public final static String[] VERTEXS={ "a","b","c","d","e","f","g","h","i"}; private final int[][] EDGEVALUE = { { 0, 4, 0, 0, 0, 0 , 0 ,8, 0}, { 4, 0, 8, 0, 0, 0 , 0 ,11, 0}, { 0, 8, 0, 7, 0, 4 , 0 ,0, 2}, { 0, 0, 7, 0, 9, 14, 0 ,0, 0}, { 0, 0, 0, 9, 0, 10, 0 ,0, 0}, { 0, 0, 4, 14, 10, 0, 2 ,0, 0}, { 0, 0, 0, 0, 0, 2, 0 ,1, 6}, { 8, 11, 0, 0, 0, 0, 1 ,0, 7}, { 0, 0, 2, 0, 0, 0, 6 ,7, 0} }; public int count; public String[] vertexstr; public int[][] edgesValue; public Graph() { this.count=NODECOUNT; this.edgesValue=EDGEVALUE; this.vertexstr=VERTEXS; } /** * 获取当前图中的所有的边集合 * @return */ public List getSortedEdgeFromTo(){ List fts = new ArrayList (); for(int i=0;i 4.2 树的存储和表示
package lbz.ch23.mst;import java.util.Comparator;import sun.misc.Compare;/** * @author LbZhang * @version 创建时间：2016年3月17日 上午5:41:52 * @description 边类 */public class FromTo{ public int weight; public TreeNode from; public TreeNode to; @Override public String toString() { return this.from.getVetex()+"->"+this.getTo().getVetex()+":"+this.weight+""; } public FromTo() { super(); } public FromTo(int weight, TreeNode from, TreeNode to) { super(); this.weight = weight; this.from = from; this.to = to; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public TreeNode getFrom() { return from; } public void setFrom(TreeNode from) { this.from = from; } public TreeNode getTo() { return to; } public void setTo(TreeNode to) { this.to = to; }} package lbz.ch23.mst;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;/** * @author LbZhang * @version 创建时间：2016年3月17日 下午3:48:34 * @description 比较类 */public class ComparatorFromTo implements Comparator{ @Override public int compare(Object o1, Object o2) { FromTo ft1 = (FromTo)o1; FromTo ft2 = (FromTo)o2; int flag = 0; if(ft1.getWeight()>=ft2.getWeight()){ flag=1; }else{ flag=-1; } return flag; } @SuppressWarnings("unchecked") public static void main(String[] args) { System.out.println("Test !@"); List fts = new ArrayList (); fts.add(new FromTo(3,new TreeNode("A"),new TreeNode("B"))); fts.add(new FromTo(1,new TreeNode("A"),new TreeNode("B"))); fts.add(new FromTo(5,new TreeNode("A"),new TreeNode("B"))); fts.add(new FromTo(2,new TreeNode("A"),new TreeNode("B"))); ComparatorFromTo cft = new ComparatorFromTo(); Collections.sort(fts, cft); for(int i=0;i package lbz.ch23.mst;import java.util.ArrayList;import java.util.List;/** * @author LbZhang * @version 创建时间：2016年3月17日 上午5:14:25 * @description 树结点类 */public class TreeNode { public String vetex; public List from = new ArrayList (); public List to = new ArrayList (); public TreeNode(String vetex) { super(); this.vetex = vetex; } public TreeNode(String vetex, List from, List to) { super(); this.vetex = vetex; this.from = from; this.to = to; } public TreeNode() { super(); } public String getVetex() { return vetex; } public void setVetex(String vetex) { this.vetex = vetex; } public List getFrom() { return from; } public void setFrom(List from) { this.from = from; } public List getTo() { return to; } public void setTo(List to) { this.to = to; }} package lbz.ch23.mst;import java.util.ArrayList;import java.util.List;/** * @author LbZhang * @version 创建时间：2016年3月17日 下午2:56:36 * @description 最小生成树结构类 */public class MSTree { public TreeNode root;//树的根节点 public List tns = new ArrayList (); public List fts=new ArrayList (); public MSTree() { super(); } public MSTree(TreeNode root) { super(); this.root = root; this.tns.add(root); } public MSTree(TreeNode r, List tns, List fts) { super(); this.root=r; this.tns = tns; this.fts = fts; } public TreeNode getRoot() { return root; } public void setRoot(TreeNode root) { this.root = root; } public List getTns() { return tns; } public void setTns(List tns) { this.tns = tns; } public List getFts() { return fts; } public void setFts(List fts) { this.fts = fts; } /** * 判断两个顶点是否在当前的最小生成树中 * @param from * @param to * @return */ public boolean containsTwoNodes(TreeNode from, TreeNode to) { boolean flag = false; int count = 0;// System.out.println(tns.size());// for(int i=0;i =2){ flag=true; break; } } return flag; } /** * 当前树中包含当前结点 * @param from * @return */ public boolean containsNode(TreeNode tn) { boolean flag = false; for(int i=0;i 4.3 克鲁斯卡尔（Krusckal）算法的实现
package lbz.ch23.mst;import java.util.ArrayList;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Set;/** * @author LbZhang * @version 创建时间：2016年3月16日 下午9:09:05 * @description MST Kruskal算法实现类 * 无向连通图——最小生成树算法的设计实现和测试 * * MinimumSpanningTree */public class KruskalMST { public static void main(String[] args) { System.out.println("My Kruskal MST TEST! "); Graph g = new Graph(); g.printMGraph(); System.out.println("----无向连通图构建完毕----"); //克鲁斯卡尔算法的最小生成树 Set frset = MstKruskal(g); Iterator it = frset.iterator(); System.out.println("----最小生成树的结果---"); while(it.hasNext()){ FromTo ft = it.next(); System.out.println(ft.getFrom().getVetex()+"->"+ft.getTo().getVetex()+": "+ ft.getWeight()); } } /** * Kruskal 算法的核心内容的实现 * @param g * @return */ private static Set MstKruskal(Graph g) { Set FRSet = new HashSet (); //最小生成树列表 MSTree mst = new MSTree(); int n=g.count;//结点的个数 List mstList = new ArrayList (); //初始化各个最小生成树 for(int i=0;i fts = g.getSortedEdgeFromTo(); for(int i=0;i "+fts.get(i).getTo().getVetex()); } System.out.println("----根据权重排序 一共有:"+fts.size()+"条边----"); for(int i=0;i mstList) { MSTree mst1 = new MSTree(),mst2=new MSTree(); int memo = 0; for(int i=0;i mstList) { boolean flag = false; for(int i=0;i 4.4 普利姆（Prim）算法的实现
package lbz.ch23.mst;import java.util.Iterator;import java.util.List;import java.util.Set;/** * @author LbZhang * @version 创建时间：2016年3月17日 下午8:21:45 * @description MST Prim算法实现类 * 无向连通图——最小生成树算法的设计实现和测试 */public class PrimMST { public static void main(String[] args) { System.out.println("My Prim MST TEST! "); Graph g = new Graph(); g.printMGraph(); System.out.println("----无向连通图构建完毕----"); MSTree mst = new MSTree(); TreeNode root = new TreeNode("a"); mst=MstPrim(g,root); System.out.println("输出Prim构造的最小生成树的结果演示"); for(int i=0;i fts = g.getSortedEdgeFromTo(); while(mst.getTns().size()<=g.getCount()){ FromTo ft = extractMin(fts,mst);// if(ft==null){ //最后一个会传出null的值 break; } mst.getTns().add(ft.to); mst.getFts().add(ft); } return mst; } private static FromTo extractMin(List fts, MSTree mst) { FromTo ft=null; TreeNode tnv = null; for(int i=0;i