最小生成树问题是贪心策略的经典应用,其中Kruskal算法用来求解边数不是特别多的(例如完全图)图的最小生成树。这里我们以无向连通图为例。
Kruskal算法的核心思想是按照边的从小到大的顺序依次加入到点集中,直到加入n-1条边,设无向连通图有n个顶点。
Kruskal算法一般包含如下重要步骤:
1. 边集按照权值由小到大的顺序排序--时间复杂度是 O(e*log(e) ) (e为边数)
2. 检查待加入的边是否和当前求得的点集构成回路--时间复杂度是 O(n) (n为当前求得点集的顶点数)
3. 点集的合并-如果用数组形式,时间复杂度是 O(n) (待加入的点所在点集合的顶点数)
由此看出,Kruskal算法总的时间复杂度主要由排序决定,所以为 O(e*log(e) ) (e为边数)。
显然,对于稀疏边的图,Kruskal算法是很适合的。
在实现算法的时候,数据结构的设计是十分重要的,特别是对于检查回路和点集的合并。合理的设计数据结构并充分利用Java的集合类将大大简化实现的难度。
主体类:
import greedyProgramming.SimpleGraphics.Edge;
import java.util.List;
/**
* 稀疏边图的最小生成树的Kruskal算法实现
* @author ql_math
*
*/
public class KruskalForMinimumSpanningTree implements MinimumSpanningTreeGeneration{
public double generateMinimumSpanningTree(double[][] graphicArray)
{
SimpleGraphics graph=new SimpleGraphics(graphicArray);
List<Edge> sortedEdges = graph.sortGraphicEdges();//按照边的长度排序(短的在前)
int n=graph.getPSize();//顶点数目
int i=0,j=0;
double shortestLength=0;
while(i<sortedEdges.size())//贪心思想加入当前权值最小的边并检查是否含有回路
{
Edge e=sortedEdges.get(i++);
Point stP=e.startPoint;
Point edP=e.endPoint;
if(stP.getBelongToList().contains(edP))//当前待加入的边加入后形成回路
continue;
stP.getBelongToList().addAll(edP.getBelongToList());//合并两个不同的点集
edP.setBelongToList(stP.getBelongToList());//保持所属集合一致性
j++;//合服要求的边数+1
shortestLength+=e.length;
if(j==n-1)
break;
}
return shortestLength;
}
/**
* @param args
*/
public static void main(String[] args) {
MinimumSpanningTreeGeneration st=new KruskalForMinimumSpanningTree();
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));
}
}
数据结构类:
SimpleGraphics类
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class SimpleGraphics {
public final static double ERROR=1e-3;
/**无向图的邻接矩阵表示*/
private int[][] adjArray;
/**无向图的数组表示*/
private double[][] graphArray;
/**点集合*/
private Point[] points;
/**点个数*/
private int pSize;
static class Edge implements Comparable<Edge>
{
Point startPoint;
Point endPoint;
double length;
Edge(Point point1,Point point2, double value)
{
startPoint=point1;
endPoint=point2;
length=value;
}
@Override
public int compareTo(Edge o) {
if(length-o.length>ERROR)
return 1;
if(o.length>ERROR)
return -1;
return 0;
}
}
/**
* 无向图的二维数组表示
* @param graphArray
*/
public SimpleGraphics(double[][] graphArray)
{
this.graphArray=graphArray;
pSize=graphArray.length;
points=new Point[pSize];
for(int i=0; i<pSize;i++)
points[i]=new Point(i);
}
/**
*
* @return
*/
public List<Edge> sortGraphicEdges()
{
List<Edge> eList=new LinkedList<Edge>();
for(int i=0;i<pSize;i++)
{
for(int j=0;j<i;j++)
{
if(graphArray[i][j]>0)
{
eList.add(new Edge(points[i],points[j],graphArray[i][j]));
}
}
}
Collections.sort(eList);
return new ArrayList<Edge>(eList);
}
public Point[] getPoints()
{
return points;
}
public void setPoints(Point[] points) {
this.points = points;
}
public void updateGraphicArray(int i, int j, double value)
{
graphArray[i][j]=value;
}
public void updateAdjacencyArray(int i, int j, int status)
{
adjArray[i][j]=status;
}
public void setGraphicArray(double[][] graphArray)
{
this.graphArray=graphArray;
}
public double[][] getGraphicArray()
{
return graphArray;
}
public int getConnectionStatus(int i, int j)
{
return adjArray[i][j];
}
public void setAdjacencyArray(int[][] adjArray)
{
this.adjArray=adjArray;
}
public int[][] getAdjacencyArray()
{
return adjArray;
}
public int getPSize() {
return pSize;
}
public void setPSize(int size) {
pSize = size;
}
/**
* 获得与当前点连接的点集合
* @param start_point
* @return
*/
public double[] getAdjacencyPoints(int start_point) {
return graphArray[start_point];
}
}
Point类
import java.util.ArrayList;
import java.util.List;
public class Point {
private int index;
/**和该点相连的点集*/
private List<Point> connectedToList;
/**该点属于的点集*/
private List<Point> belongToList=new ArrayList<Point>();
public Point(int index)
{
this.index=index;
belongToList.add(this);
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public List<Point> getBelongToList() {
return belongToList;
}
public void setBelongToList(List<Point> belongToList) {
this.belongToList = belongToList;
}
public void setConnectedToList(List<Point> connectedToList) {
this.connectedToList = connectedToList;
}
public List<Point> getConnectedToList() {
return connectedToList;
}
}
分享到:
相关推荐
图论- 生成树- 最小生成树- Kruskal.rar
代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal...
代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树...
最小生成树Kruskal算法[定义].pdf
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
最小生成树kruskal算法 最小生成树kruskal算法
对给定的图结构,实现求解最小生成树的Kruskal算法。每次在满足和已选边不构成回路的条件下选择一条权植最小的边,添加到新的生成数中。Kruskal算法的实现类似于计算连通枝的算法。它使用了分离集合数据结构以保持数...
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
实现了kruskal的算法,测试可行。
。。。
。。。
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
prim算法 Kruskal算法分别实现最小生成树
最小生成树的kruskal算法(c++源码)
数据结构课程设计报告最小生成树Kruskal算法
matlab-Kruskal算法求最小生成树问题.zip
最小生成树kruskal算法并查集版 C语言实现 - Slyar Home
Prim算法与Kruskal算法 求最小生成树 源代码 实验报告 完整
第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小生成树的克鲁斯卡尔(Kruskal)算法 稳过 生成树是将图中所有顶点以最少的边连通的子图。权值和最小的生成树就是最小...
该程序是我写的博客“一起talk C栗子吧(第五十回:C语言实例--最小生成树二)”的配套程序,共享给大家使用