当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

java 图论三 带权图的最小生成树 Prim算法

发表于: 2012-11-22   作者:blackproof   来源:转载   浏览次数:
摘要: 带权图是实际情况中经常使用的,如城市道路,etl优化等等。   在带权图中经常遇到的问题就是生成最小生成树,就是加权总值最小的路径,这里用prime算法实现   prim算法的总思路   /** * 生成最小生成树 * 将顶点放到树集合中,重复一下操作 * 1.找到最新的vertex到其他vertex的所有edge,其他vertex不能在

带权图是实际情况中经常使用的,如城市道路,etl优化等等。

 

在带权图中经常遇到的问题就是生成最小生成树,就是加权总值最小的路径,这里用prime算法实现

 

prim算法的总思路

 

/**
	 * 生成最小生成树
	 * 将顶点放到树集合中,重复一下操作
	 * 1.找到最新的vertex到其他vertex的所有edge,其他vertex不能在树集合中,把这些edge放到优先队列中
	 * 2.找到权值最小的边,把edge和edge所到达的vertex放到树集合中
	 */

 

 

prim算法的过程示意图:这里贴一个邮电大学的

http://resource.jingpinke.com/details?uuid=ff808081-29263667-0129-2636a17d-39cb&objectId=oid:ff808081-29263667-0129-2636a17d-39cc

 

prim算法代码,java实现:

 

 

package com.Construction.DiscrectGraph;

import java.io.ObjectOutputStream.PutField;

public class Graph {
	/**
	 * max vertx number
	 */
	private final int MAX_VERTX = 20;
	/**
	 * max distance value
	 */
	private final int INFINITY  = 1000000;
	/**
	 * node list
	 */
	private Vertex vertexList[];
	/**
	 * adjacency matrix
	 */
	private int adjMat[][];
	/**
	 * graph node number
	 */
	private int nVerts;
	/**
	 * prime tree number
	 */
	private int nTree;
	/**
	 * current tree node
	 */
	private int currentVert;
	
	private PriorityQ priorityQueue;
	
	public Graph(){
		vertexList = new Vertex[MAX_VERTX];
		adjMat = new int[MAX_VERTX][MAX_VERTX];
		nVerts = 0;
		for (int i = 0; i < MAX_VERTX; i++) {
			for (int j = 0; j < MAX_VERTX; j++) {
				adjMat[i][j] = INFINITY;
			}
		}
		priorityQueue = new PriorityQ();
	}
	
	/**
	 * 添加元素
	 * @param label
	 */
	public void addVertex(char label){
		//添加元素,并将计数器加一
		vertexList[nVerts++] = new Vertex(label);
	}
	
	/**
	 * 添加边
	 * @param sv
	 * @param dv
	 * @param dis
	 */
	public void addEdge(int sv,int dv,int dis){
		adjMat[sv][dv] = dis;
		adjMat[dv][sv] = dis;
	}
	
	
	/**
	 * 生成最小生成树
	 * 将顶点放到树集合中,重复一下操作
	 * 1.找到最新的vertex到其他vertex的所有edge,其他vertex不能在树集合中,把这些edge放到优先队列中
	 * 2.找到权值最小的边,把edge和edge所到达的vertex放到树集合中
	 */
	public void mstw(){
		currentVert = 0;
		while (nTree < nVerts -1) {
			vertexList[currentVert].isInTree = true;//步骤2,放到树中
			nTree ++;
			for (int i = 0; i < nVerts; i++) {
				if(i == currentVert) continue; // visit other graph node
				if(vertexList[i].isInTree) continue;//visit other graph don't contain in tree -- to avoid connect unneccessary node
				int dis = adjMat[currentVert][i];
				if (dis == INFINITY) continue;
				putInPQ(i, dis);
			}
			if (priorityQueue.getSize() == 0) {
				return;
			}
			
			Edge currentMinEdge  = priorityQueue.removeMin();
			int sVert = currentMinEdge.srcVert;
			currentVert = currentMinEdge.destVert;
			System.out.println(vertexList[sVert].label);
			System.out.println(vertexList[currentVert].label);
			System.out.println(" ");
		}
		for (int i = 0; i < nVerts; i++) {
			vertexList[i].isInTree = false;
		}
	}
	
	/**
	 * 将循环操作1中的edge,放入优先队列中
	 * 优先队列中,到一个目的的边是唯一滴,所有当已经有老边了,需要比较替代
	 * @param vertex
	 * @param dis
	 */
	public void putInPQ(int vertex,int dis){
		int index = priorityQueue.find(vertex);
		if(index != -1){
			Edge tempEdge = priorityQueue.peek(index);
			int oldDis = tempEdge.distance;
			if(oldDis > dis){
				priorityQueue.remove(index);
				Edge theEdge = new Edge(currentVert, vertex, dis);
				priorityQueue.insert(theEdge);
			}
		}else{
			Edge theEdge = new Edge(currentVert, vertex, dis);
			priorityQueue.insert(theEdge);
		}
	}
	
	    public static void main(String[] args){  
	        Graph g = new Graph();  
	        g.addVertex('A');  
	        g.addVertex('B');  
	        g.addVertex('C');  
	        g.addVertex('D');  
	        g.addVertex('E');  
	        g.addVertex('F');  
	          
	        g.addEdge(0, 1, 6);  
	        g.addEdge(0, 3, 4);  
	        g.addEdge(1, 2, 10);  
	        g.addEdge(1, 3, 7);  
	        g.addEdge(1, 4, 7);  
	        g.addEdge(2, 3, 8);  
	        g.addEdge(2, 4, 5);  
	        g.addEdge(2, 5, 6);  
	        g.addEdge(3, 4, 12);  
	        g.addEdge(4, 5, 7);  
	        g.mstw();  
	    }  

}
 

 

java 图论三 带权图的最小生成树 Prim算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
在一个具有几个顶点的连通图G中,如果存在子图G'包含G中所有顶点和一部分边,且不形成回路,则称G'
  定义:设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E’)是一棵树,则称T是G的一棵生成树(Sp
prim算法是生成最小生成树的一个重要方法,它非常类似于最短路径的Dijastra算法. Prim算法的特点是
Prim算法 1 .概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意
1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法
import java.util.Scanner; 方法一:时间复杂度O(n^3) class Edge { /** * 边的起点 */ char vexa;
  文章作者:ktyanny 文章来源:ktyanny 转载请注明,谢谢合作。      ktyanny最近很心烦,因
题目1 : 最小生成树三·堆优化的Prim算法 时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB 描述
-- 图论写到这,基本概念也就告一段落了,之后还会贴一些我在工作中设计的图 -- 图论一 http://blac
-- 图论写到这,基本概念也就告一段落了,之后还会贴一些我在工作中设计的图 -- 图论一 http://blac
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号