在上一篇中,我们提到了用来求解边数不是特别多的(例如完全图)生成最小生成树的Kruskal算法。对于稠密图,Kruskal算法的效率不高,这时候我们可以用同样经典的Prim算法求解最小生成树问题。
Prim算法的核心思想是按照当前点集到还未加入的点集的最短边来加入新的点,直到加入n个点来得到最小生成树,设无向连通图有n个顶点。
Prim算法一般包含如下重要步骤:
1. 任意选定一个初始点作为当前点集
2. 求当前点集到还未加入的点集的最短边,并把对应的点加入到当前点集--时间复杂度是 O(n^2)
由此看出,Prim算法总的时间复杂度主要由求点集间最短边决定,所以为 O(n^2) 。
同样,合理的数据结构对于算法的实现十分重要。
主体类:
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 稠密边图的最小生成树的Prim算法实现
* @author ql_math
*
*/
public class PrimForMinimumSpanningTree implements MinimumSpanningTreeGeneration{
/**最小生成树的边的连接*/
private int[][] connectionSatus;
public double generateMinimumSpanningTree(double[][] graphicArray) {
int start_point=1;//可以任意选择一个初始点,这里选择第一个点
SimpleGraphics graph=new SimpleGraphics(graphicArray);
List<Integer> current_set=new LinkedList<Integer>();//当前点集合
current_set.add(start_point);
initPointsConnectionSatus(graph.getPSize(),start_point);//初始化最小生成树的边的连接
int i=1;
double shortestLength=0;
while(i<graph.getPSize())//贪心思想加入和当前点集合最近距离的某个点p
{
shortestLength+=getShortestPointsPair(connectionSatus, current_set,graph);
i++;
}
return shortestLength;
}
public int[][] getConnectionSatus() {
return connectionSatus;
}
/**
* 获得和当前点集合最近距离的某个点p,返回对应的距离
* @param connectionSatus
* @param current_set
* @param graph
* @return
*/
private double getShortestPointsPair(int[][] connectionSatus, List<Integer> current_set, SimpleGraphics graph) {
double minLength=Double.MAX_VALUE;
int[] pair=new int[2];
for(Integer i:current_set)
{
double[] arr=graph.getAdjacencyPoints(i);//获得与当前点连接的点集合
for(int j=0; j<graph.getPSize();j++)
{
if(arr[j]>graph.ERROR&&!current_set.contains(j))
{
if(arr[j]<minLength)
{
minLength=arr[j];
pair[1]=j;
pair[0]=i;
}
}
}
}
current_set.add(pair[1]);//加入新的点
connectionSatus[pair[1]][1]=pair[0];//更新最小生成树的边的连接
return minLength;
}
/**
* 初始化最小生成树的边的连接(所有点都与初始选择点连接)
* @param graph
* @param start_point
* @return
*/
private int[][] initPointsConnectionSatus(int pSize,
int start_point) {
connectionSatus=new int[pSize][2];
for(int i=0;i<pSize;i++)
connectionSatus[i]=new int[]{i,start_point};
return connectionSatus;
}
public String toString()
{
StringBuffer stf=new StringBuffer();
for(int[] i: connectionSatus)
{
stf.append(Arrays.toString(i)+"\r\n");
}
return stf.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
MinimumSpanningTreeGeneration st=new PrimForMinimumSpanningTree();
double[][] graphicArray={{0,0,300,80,50},{0,0,70,75,200},
{300,70,0,60,0},{80,75,60,0,90},{50,200,0,90,0}};
System.out.println("最小生成树的权值和是:"+st.generateMinimumSpanningTree(graphicArray));
System.out.println("最小生成树的连接情况是:\r\n"+st.toString());
}
}
分享到:
相关推荐
利用c++编程实现,最小生成树的Prim算法,
代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小...
用字符文件提供数据建立连通带权网络邻接矩阵存储¬¬结构。编写程序,用Prim算法求一棵最小生成树。要求输出最小生成树的各条边(用顶点无序偶表示)、各条边上的权值、最小生成树所有边上的权值之和。
最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++
图论- 生成树- 最小生成树- Prim.rar
使用Prim算法编写的最小生成树(C语言),为更好地学习数据结构
讲述如何实现最小生成树,及C#daima实现
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
基于MATLAB的最小生成树Prim算法 源代码程序.rar
。。。
实现构造最小生成树的Prim算法
prim算法 Kruskal算法分别实现最小生成树
/2,Prim算法的描述:// 假如N=(V,{E})是连通网,TE是N上最小生成树中边得集合。算法从U={u0}(u0是V中的元素),TE={}开始,重复执行下述操作:// 在所有u属于U,v属于V-U的边(u,v)属于E中找一条代价最小的边...
python实现prim 最小生成树算法 源码
最小生成树prim最小生成树prim最小生成树prim最小生成树prim
普里姆算法通过寻找无向图中权值最小的边,并且将其组合成最小生成树,也就是图的相对最短路径,同时将最小生成树以点集的形式输出,便于观察
最小生成树,Prim算法的使用(邻接矩阵实现)
数据结构教程实验--用Prim算法构造最小生成树
最小生成树的prim算法
第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小...