面向对象方式实现最小生成树算法
程序员文章站
2022-05-14 18:58:26
...
最小生成树
一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。
最小生成树可参考:http://baike.baidu.com/view/288214.htm
下面实现最小生成树的Prim算法。
网上包括很多论坛里实现最小生成树的算法多为二维数组、面向过程的方式。最近得闲试着用Java代码实现面向对象的最小生成树算法。这样从实用角度看至少没那么书卷气了。
准备工作:
点、边、图的实现
点
普通边
权重
带权边
图
Prim算法
Prim算法实现的是找出一个有权重连通图中的最小生成树,即:具有最小权重且连接到所有结点的树。
首先以一个结点作为最小生成树的初始结点,然后以迭代的方式找出与最小生成树中各结点权重最小边,并加入到最小生成树中。加入之后如果产生回路则跳过这条边,选择下一个结点。当所有结点都加入到最小生成树中之后,就找出了连通图中的最小生成树了。
Java实现:
测试结果
边权重一样的图
边权重不一样的图
以上代码还有重构优化的余地,如:计算顶点的度,获取权重最小边可移入图类中;点是否在边中可移入边类中;图是否有环的代码看起来不够一目了然等。
另外最小生成树算法还有Kruskal算法;Dijkstra(迪杰斯特拉)算法也可以用来实现最小生成树程序。
以后有空再实现之。
参考资料:
可从下面链接找到我的测试用例所用的图,以及Prim算法的解释
http://squirrelrao.iteye.com/blog/1044867
可从下面链接找到无向图的环查找算法:
http://blog.csdn.net/sunmenggmail/article/details/7324646
一个有 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) * 只有点描述相同的点是相同的 */ @Override public boolean equals(Object obj) { if(obj instanceof Point){ if(((Point) obj).point.equals(this.point)){ return true; } } return false; } @Override public 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) * 只有起止点相同的边才是同一条边 */ @Override public 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; } @Override public 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; } @Override public int compareTo(Weight o) { if(o.weight == this.weight){ return 0; }else if(o.weight > this.weight){ return -1; }else{ return 1; } } @Override public boolean equals(Object obj) { if(obj instanceof Weight){ if(((Weight) obj).weight == this.weight){ return true; } } return false; } @Override public 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; } @Override public int compareTo(EdgeWithWeight o) { return o.weight.compareTo(this.weight); } public Weight getWeight() { return weight; } public void setWeight(Weight weight) { this.weight = weight; } @Override public 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; } @Override public 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; } @Override public String toString() { return "Graph [pointList=" + pointList + ", edgeList=" + edgeList + "]"; } @Override public 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) { } }
Prim算法
Prim算法实现的是找出一个有权重连通图中的最小生成树,即:具有最小权重且连接到所有结点的树。
首先以一个结点作为最小生成树的初始结点,然后以迭代的方式找出与最小生成树中各结点权重最小边,并加入到最小生成树中。加入之后如果产生回路则跳过这条边,选择下一个结点。当所有结点都加入到最小生成树中之后,就找出了连通图中的最小生成树了。
Java实现:
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]]]]
以上代码还有重构优化的余地,如:计算顶点的度,获取权重最小边可移入图类中;点是否在边中可移入边类中;图是否有环的代码看起来不够一目了然等。
另外最小生成树算法还有Kruskal算法;Dijkstra(迪杰斯特拉)算法也可以用来实现最小生成树程序。
以后有空再实现之。
参考资料:
可从下面链接找到我的测试用例所用的图,以及Prim算法的解释
http://squirrelrao.iteye.com/blog/1044867
可从下面链接找到无向图的环查找算法:
http://blog.csdn.net/sunmenggmail/article/details/7324646