`
zhuyufufu
  • 浏览: 139517 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论
阅读更多
最小生成树
     一个有 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
1
0
分享到:
评论

相关推荐

    图的最小生成树Prim算法C++面向对象实现.doc

    Prim算法是求解最小生成树的一种经典算法,由Vojtěch Jarník、Karl Menger和Joseph Kruskal等人独立提出,但以Ernesto Prim的名字最为人所知。 Prim算法的基本思想是从图中任意一个节点开始,逐步添加边,使得...

    遗传算法求解最小生成树问题VC代码

    在VC++环境下,实现遗传算法求解最小生成树,首先需要理解遗传算法的基本流程:初始化种群、选择、交叉、变异以及适应度计算。以下是对这个过程的详细说明: 1. 初始化种群:随机生成一组可能的解,每个解可以看作...

    数据结构 最小生成树C代码

    3. 最小生成树的生成:我们使用了一个名为MFSet的类来实现克鲁斯卡尔算法,该类中包括了两个主要函数:root函数用于查找元素的根节点,Tmerge函数用于合并两个集合。我们使用了一个名为main的函数来调用这些函数,...

    最小生成树实验报告

    这是因为C++提供了灵活的内存管理和面向对象的编程特性,非常适合于处理图这种复杂数据结构的算法实现。实验中编写的程序包含了数据结构的定义,例如`Edge`结构体用于存储边的信息,以及`seek`函数用于查找顶点所属...

    最小生成树 mfc c++

    在实现最小生成树算法时,C++提供了高效的数据结构(如数组、链表)和算法实现工具。 对于给定的描述,“输入顶点和权,显示邻接矩阵”意味着程序可能包含以下功能: 1. 用户输入:允许用户输入顶点的数量和它们...

    数据结构报告——最小生成树

    最小生成树算法的目标是从一个加权无向图中找到一棵包括所有顶点的树,使得这棵树的所有边的权重之和尽可能小。这样的树被称为最小生成树。在实际应用中,这个概念广泛应用于电信网络规划、电路设计和运输路线规划等...

    使用Java实现的基于最小生成树的旅行商问题.zip

    Java作为一种广泛使用的面向对象编程语言,具有丰富的类库和强大的跨平台能力,非常适合用于这样的算法实现。在实现过程中,可能会用到`java.util`包中的数据结构,如ArrayList或LinkedList来存储城市和边,以及优先...

    最小生成树 matlab Kruskal 源代码

    在提供的压缩包文件“最小生成树”中,很可能包含了一个名为“最小生成树”的MATLAB源代码文件,这个文件应该实现了上述的Kruskal算法。通过阅读和理解这段代码,你可以深入学习Kruskal算法的细节,以及如何在MATLAB...

    JS使用Prim算法和Kruskal算法实现最小生成树

    在介绍的文档中,主要讲解了如何用JavaScript(JS)实现两种著名的最小生成树算法:Prim算法和Kruskal算法。 ### Prim算法 Prim算法是由Vojtěch Jarník提出,后由Robert Prim推广的贪心算法,其核心思想是从图中...

    基于最小生成树算法的南昌地铁票价查询C++代码

    基于最小生成树算法的南昌地铁票价查询C++代码(C++ code of Nanchang subway fare query based on minimum spanning tree algorithm)C++是一种广泛使用的编程语言,它是由Bjarne Stroustrup于1979年在新泽西州...

    java实现一些基本的算法,如快速排序,BFS,N皇后,最小生成树等

    在Java中实现这些算法时,可以利用其丰富的数据结构(如数组、链表、队列、堆等)和面向对象的特性,使得代码更加清晰和高效。通过实践这些算法,不仅能加深对它们的理解,还能提升编程技巧,为解决更复杂的问题打下...

    最小生成树图形化实现

    在实际应用中,如构建通信网络、设计高效的公路系统等,最小生成树算法有着广泛的应用。本项目是使用C++的MFC(Microsoft Foundation Classes)框架实现最小生成树的图形化表示,适合于数据结构学习者和编程爱好者...

    C++实现最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

    1、最小生成树的概念; 2、Prim算法及其实现; 3、Kruskal算法及其实现; 4、图的表示; 5、边的表示; 6、优先队列priority_queue的自定义排序 7、大根堆、小根堆的区别 8、结构体的构建 面向对象: 有一定C++基础...

    数据结构 最小生成树 无向图 连通图 MFC c语言

    在提供的压缩包中,"最小生成树"可能是一个源代码文件或文档,详细解释了如何实现最小生成树的算法;"sure"可能是程序的可执行文件或者项目的配置文件。如果你正在学习这方面的知识,通过分析和运行这些文件,你将能...

    最小生成树

    最小生成树(Minimum Spanning Tree, MST)是图论中的一个重要概念,主要应用于网络设计、数据传输优化等领域。在这个场景中,我们提到的MST是用MFC(Microsoft Foundation Classes)编程实现的一个程序,用于解决...

    ChuLiuEdmonds:Tarjan 的 Chu-Liu-Edmonds 算法实现,用于寻找密集图的最小最大生成树

    在图论领域,寻找图的最小生成树是解决网络优化问题的关键之一。Chu-Liu/Edmonds算法,也被称为Kruskal's算法的一个变种,特别适用于寻找有向加权图的最小最大生成树。本文将深入探讨该算法的原理,并重点介绍由...

    软件设计师教程(第3版)算法设计和面向对象篇

    例如,霍夫曼编码和Prim最小生成树算法。 4. **回溯法**:在解决问题时尝试所有可能的解决方案,但一旦发现错误就回溯。如八皇后问题、数独等。 5. **分治策略**:将大问题分解为小问题来求解,如快速排序、归并...

    数据结构(用面向对象方法与C++语言描述)课后答案

    - **图**:图的表示(邻接矩阵、邻接表),图的遍历(深度优先搜索、广度优先搜索),最小生成树(Prim算法、Kruskal算法)。 - **排序**:冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等比较和实现...

    C++ 就简单算法实现大全

    除了基本算法,本书还可能涉及字符串处理、图形和几何算法、图论算法(如最短路径算法Dijkstra和最小生成树算法Prim)以及回溯法、贪心算法等。这些算法在实际问题中有着广泛的应用,例如网络路由、物流优化、游戏...

Global site tag (gtag.js) - Google Analytics