面向对象方式实现最小生成树算法
最小生成树
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
最小生成树可参考：http://baike.baidu.com/view/288214.htm
下面实现最小生成树的Prim算法。
网上包括很多论坛里实现最小生成树的算法多为二维数组、面向过程的方式。最近得闲试着用Java代码实现面向对象的最小生成树算法。这样从实用角度看至少没那么书卷气了。
准备工作：
点、边、图的实现
点
package com.zas.test.tree;/** * 点的定义 暂时为一个标记类 如果有现实的业务需求 再添加点的属性定义 * @author zas */public class Point {//暂时定义为字符串标记String point;public Point() {super();}public Point(String point) {super();this.point = point;}public String getPoint() {return point;}public void setPoint(String point) {this.point = point;}/* (non-Javadoc) * @see java.lang.Object#equals(java.lang.Object) * 只有点描述相同的点是相同的 */@Overridepublic boolean equals(Object obj) {if(obj instanceof Point){if(((Point) obj).point.equals(this.point)){return true;}}return false;}@Overridepublic String toString() {return "Point [point=" + point + "]";}/** * @param args */public static void main(String[] args) {}}package com.zas.test.tree;/** * 边的定义 * @author zas */public class Edge {//起点protected Point startPoint;//终点protected Point endPoint;public Edge() {super();}public Edge(Point startPoint, Point endPoint) {super();this.startPoint = startPoint;this.endPoint = endPoint;}public Point getStartPoint() {return startPoint;}public void setStartPoint(Point startPoint) {this.startPoint = startPoint;}public Point getEndPoint() {return endPoint;}public void setEndPoint(Point endPoint) {this.endPoint = endPoint;}/* (non-Javadoc) * @see java.lang.Object#equals(java.lang.Object) * 只有起止点相同的边才是同一条边 */@Overridepublic boolean equals(Object obj) {if(obj instanceof Edge){Edge outEdge = (Edge)obj;if(outEdge.startPoint.equals(this.startPoint)){if(outEdge.endPoint.equals(this.endPoint)){return true;}}}return false;}@Overridepublic String toString() {return "Edge [startPoint=" + startPoint + ", endPoint=" + endPoint+ "]";}/** * @param args */public static void main(String[] args) {}}package com.zas.test.tree;/** * 权重的定义 * @author zas */public class Weight implements Comparable<Weight>{//double类型定义一个权重信息double weight = 0.0;public Weight() {super();}public Weight(double weight) {super();this.weight = weight;}@Overridepublic int compareTo(Weight o) {if(o.weight == this.weight){return 0;}else if(o.weight > this.weight){return -1;}else{return 1;}}@Overridepublic boolean equals(Object obj) {if(obj instanceof Weight){if(((Weight) obj).weight == this.weight){return true;}}return false;}@Overridepublic String toString() {return "Weight [weight=" + weight + "]";}/** * @param args */public static void main(String[] args) {}}package com.zas.test.tree;public class EdgeWithWeight extends Edge implements Comparable<EdgeWithWeight> {//边的权重Weight weight;public EdgeWithWeight() {super();}public EdgeWithWeight(Point startPoint, Point endPoint) {super(startPoint, endPoint);}public EdgeWithWeight(Weight weight) {super();this.weight = weight;}public EdgeWithWeight(Point startPoint, Point endPoint, Weight weight) {super(startPoint, endPoint);this.weight = weight;}@Overridepublic int compareTo(EdgeWithWeight o) {return o.weight.compareTo(this.weight);}public Weight getWeight() {return weight;}public void setWeight(Weight weight) {this.weight = weight;}@Overridepublic boolean equals(Object obj) {if(obj instanceof EdgeWithWeight){if(((EdgeWithWeight) obj).getStartPoint().equals(this.getStartPoint())){if(((EdgeWithWeight) obj).getEndPoint().equals(this.getEndPoint())){if(((EdgeWithWeight) obj).getWeight().equals(this.getWeight())){return true;}}}}return false;}@Overridepublic String toString() {return "EdgeWithWeight [weight=" + weight + ", startPoint="+ startPoint + ", endPoint=" + endPoint + "]";}/** * @param args */public static void main(String[] args) {}}package com.zas.test.tree;import java.util.ArrayList;import java.util.List;/** * 图的定义 * @author zas */public class Graph {//图的点列表List<Point> pointList;//图的边列表List<EdgeWithWeight> edgeList;public Graph() {super();}public Graph(List<Point> pointList, List<EdgeWithWeight> edgeList) {super();this.pointList = pointList;this.edgeList = edgeList;}/** * 添加一个点到图中 * @param p */public void addPoint(Point p) {if(pointList == null){pointList = new ArrayList<Point>();}pointList.add(p);}/** * 从图中删除一个点 * @param p */public void removePoint(Point p){for (Point point : pointList) {if(p.equals(point)){pointList.remove(point);break;}}}/** * 添加一条边到图中 * @param p */public void addEdge(EdgeWithWeight e) {if(edgeList == null){edgeList = new ArrayList<EdgeWithWeight>();}edgeList.add(e);}/** * 从图中删除一条边 * @param p */public void removeEdge(EdgeWithWeight e) {for (EdgeWithWeight edge : edgeList) {if(e.equals(edge)){edgeList.remove(edge);break;}}}/** * 点是否存在于图中 * @param p * @return */public boolean isPointInGraph(Point p) {if(null == pointList || pointList.size() < 1){return false;}for (Point point : pointList) {if(p.equals(point)){return true;}}return false;}/** * 点是否存在于图中 * @param p * @return */public boolean isEdgeInGraph(EdgeWithWeight e) {if(null == edgeList || edgeList.size() < 1){return false;}for (EdgeWithWeight edge : edgeList) {if(e.equals(edge)){return true;}}return false;}public List<Point> getPointList() {return pointList;}public void setPointList(List<Point> pointList) {this.pointList = pointList;}public List<EdgeWithWeight> getEdgeList() {return edgeList;}public void setEdgeList(List<EdgeWithWeight> edgeList) {this.edgeList = edgeList;}@Overridepublic String toString() {return "Graph [pointList=" + pointList + ", edgeList=" + edgeList + "]";}@Overridepublic Graph clone() {Graph g = new Graph();for (Point p : pointList) {g.addPoint(p);}for (EdgeWithWeight e : edgeList) {g.addEdge(e);}return g;}/** * @param args */public static void main(String[] args) {}}package com.zas.test.tree;import java.util.ArrayList;import java.util.List;/** * Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。 * @author zas */public class Prim {//一个要找最小生成树的图Graph graph;public Prim(Graph graph) {super();this.graph = graph;}public Graph getGraph() {return graph;}public void setGraph(Graph graph) {this.graph = graph;}/** * 首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边， * 并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。 * 当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。 * @return */public Graph prim() {Graph minTree = new Graph();for (Point p : graph.getPointList()) {minTree.addPoint(p);//获得该点的最小权重边EdgeWithWeight edge = getMinWeightEdgeForPoit(p, minTree);if(null != edge){//添加该边到最小生成树minTree.addEdge(edge);//检测是否产生回路if(isGraphHasCircle(minTree)){minTree.removeEdge(edge);}}}return minTree;}/** * 检测是否产生回路 如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。 n算法： 第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。 第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。 如果最后还有未删除顶点，则存在环，否则没有环。 n算法分析： 由于有m条边，n个顶点。 i)如果m>=n，则根据图论知识可直接判断存在环路。（证明：如果没有环路，则该图必然是k棵树 k>=1。根据树的性质，边的数目m = n-k。k>=1，所以：m<n） ii)如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。这两种操作的总数不会超过m+n。由于m<n，所以算法复杂度为O(n)。 * @param minTree * @return */private boolean isGraphHasCircle(Graph minTree) {//若图中没有顶点，或者只有一个顶点则没有回路if(minTree.getPointList() == null || minTree.getPointList().size() < 2){return false;}if(minTree.getEdgeList().size() > minTree.getPointList().size()){return true;}Graph g = minTree.clone();int pointsLeftCount = g.getPointList().size();while(pointsLeftCount > 0){//一次遍历如没有删除一个度小于2的点，则结束循环boolean endFlag = true;Point pointForRemove = null;for (Point p : g.getPointList()) {//计算顶点的度if(getCountForPoint(p, g) <= 1){//为了规避最后一个顶点被删除是的并发异常 采用标记删除pointForRemove = p;//删除之后从新遍历顶点endFlag = false;break;}}if(endFlag){break;}else{g.removePoint(pointForRemove);List<EdgeWithWeight> edgeForRemoveList = new ArrayList<EdgeWithWeight>();for (EdgeWithWeight e : g.getEdgeList()) {if(isPointInEdge(pointForRemove, e)){edgeForRemoveList.add(e);}}for (EdgeWithWeight edgeWithWeight : edgeForRemoveList) {g.removeEdge(edgeWithWeight);}}pointsLeftCount = g.getPointList().size();}if(g.getPointList().size() > 0){return true;}else{return false;}}/** * 计算顶点的度 * @param p * @return */private int getCountForPoint(Point p, Graph g) {int count = 0;for (EdgeWithWeight e : g.getEdgeList()) {if(isPointInEdge(p, e)){count = count + 1;}}return count;}/** * 获取权重最小边 * @param p * @param minTree * @return */private EdgeWithWeight getMinWeightEdgeForPoit(Point p, Graph minTree) {EdgeWithWeight e = null;for (EdgeWithWeight edge : graph.getEdgeList()) {if(!minTree.isEdgeInGraph(edge)){if(isPointInEdge(p, edge)){if(e == null){e = edge;}else{if(e.compareTo(edge) == -1){e = edge;}}}}}return e;}/** * 点是否在边中 * @param p * @param edge * @return */private boolean isPointInEdge(Point p, EdgeWithWeight edge) {if(p.equals(edge.getStartPoint()) || p.equals(edge.getEndPoint())){return true;}return false;}/** * @param args */public static void main(String[] args) {//构建一个图Graph graph = new Graph();Point a = new Point("A");Point b = new Point("B");Point c = new Point("C");Point d = new Point("D");Point e = new Point("E");Point f = new Point("F");graph.addPoint(a);graph.addPoint(b);graph.addPoint(c);graph.addPoint(d);graph.addPoint(e);graph.addPoint(f);//所有边权重相同graph.addEdge(new EdgeWithWeight(a, b, new Weight()));graph.addEdge(new EdgeWithWeight(a, c, new Weight()));graph.addEdge(new EdgeWithWeight(a, d, new Weight()));graph.addEdge(new EdgeWithWeight(b, c, new Weight()));graph.addEdge(new EdgeWithWeight(b, e, new Weight()));graph.addEdge(new EdgeWithWeight(c, d, new Weight()));graph.addEdge(new EdgeWithWeight(c, e, new Weight()));graph.addEdge(new EdgeWithWeight(c, f, new Weight()));graph.addEdge(new EdgeWithWeight(d, f, new Weight()));graph.addEdge(new EdgeWithWeight(e, f, new Weight()));Prim prim = new Prim(graph);Graph minTree = prim.prim();System.out.println(minTree);Graph graphWithWeight = new Graph();graphWithWeight.addPoint(a);graphWithWeight.addPoint(b);graphWithWeight.addPoint(c);graphWithWeight.addPoint(d);graphWithWeight.addPoint(e);graphWithWeight.addPoint(f);graphWithWeight.addEdge(new EdgeWithWeight(a, b, new Weight(6)));graphWithWeight.addEdge(new EdgeWithWeight(a, c, new Weight(1)));graphWithWeight.addEdge(new EdgeWithWeight(a, d, new Weight(5)));graphWithWeight.addEdge(new EdgeWithWeight(b, c, new Weight(5)));graphWithWeight.addEdge(new EdgeWithWeight(b, e, new Weight(3)));graphWithWeight.addEdge(new EdgeWithWeight(c, d, new Weight(7)));graphWithWeight.addEdge(new EdgeWithWeight(c, e, new Weight(5)));graphWithWeight.addEdge(new EdgeWithWeight(c, f, new Weight(4)));graphWithWeight.addEdge(new EdgeWithWeight(d, f, new Weight(2)));graphWithWeight.addEdge(new EdgeWithWeight(e, f, new Weight(6)));Prim primForWeigtTree = new Prim(graphWithWeight);Graph minTreeForWeightTree = primForWeigtTree.prim();System.out.println(minTreeForWeightTree);}}Graph [pointList=[Point [point=A], Point [point=B], Point [point=C], Point [point=D], Point [point=E], Point [point=F]], edgeList=[EdgeWithWeight [weight=Weight [weight=0.0], startPoint=Point [point=A], endPoint=Point [point=B]], EdgeWithWeight [weight=Weight [weight=0.0], startPoint=Point [point=B], endPoint=Point [point=C]], EdgeWithWeight [weight=Weight [weight=0.0], startPoint=Point [point=A], endPoint=Point [point=D]], EdgeWithWeight [weight=Weight [weight=0.0], startPoint=Point [point=B], endPoint=Point [point=E]], EdgeWithWeight [weight=Weight [weight=0.0], startPoint=Point [point=C], endPoint=Point [point=F]]]]
Graph [pointList=[Point [point=A], Point [point=B], Point [point=C], Point [point=D], Point [point=E], Point [point=F]], edgeList=[EdgeWithWeight [weight=Weight [weight=1.0], startPoint=Point [point=A], endPoint=Point [point=C]], EdgeWithWeight [weight=Weight [weight=3.0], startPoint=Point [point=B], endPoint=Point [point=E]], EdgeWithWeight [weight=Weight [weight=4.0], startPoint=Point [point=C], endPoint=Point [point=F]], EdgeWithWeight [weight=Weight [weight=2.0], startPoint=Point [point=D], endPoint=Point [point=F]], EdgeWithWeight [weight=Weight [weight=5.0], startPoint=Point [point=C], endPoint=Point [point=E]]]]
