这篇文章实现最小生成树的Kruskal算法
Kruskal算法：
Kruskal算法思想不同于Prim算法，Kruskal算法是一种按照连通网中边的权值的递增顺序构造最小生成树的算法。
Kruskal算法的基本步骤 :
假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树。
令集合U的初值为U=V，即包含有G中全部顶点，集合TE的初值为TE={}。
然后，将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；
若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止，此时的T即为最小生成树。
另外对上一篇文章中的程序进行了重构优化。
展示代码如下：
点是否在边中调整到边类
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 p
* @param edge
* @return
*/
public boolean isPointInEdge(Point p) {
if(p.equals(this.getStartPoint()) || p.equals(this.getEndPoint())){
return true;
}
return false;
}
/**
* @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;
}
/**
* 检测是否产生回路
如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=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 this
* @return
*/
public boolean isGraphHasCircle() {
//若图中没有顶点，或者只有一个顶点则没有回路
if(this.getPointList() == null || this.getPointList().size() < 2){
return false;
}
if(this.getEdgeList().size() > this.getPointList().size()){
return true;
}
Graph g = this.clone();
int pointsLeftCount = g.getPointList().size();
while(pointsLeftCount > 0){
//一次遍历如没有删除一个度小于2的点，则结束循环
boolean endFlag = true;
Point pointForRemove = null;
for (Point p : g.getPointList()) {
//计算顶点的度
if(g.getCountForPoint(p) <= 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(e.isPointInEdge(pointForRemove)){
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) {
int count = 0;
for (EdgeWithWeight e : this.getEdgeList()) {
if(e.isPointInEdge(p)){
count = count + 1;
}
}
return count;
}
/**
* @param args
*/
public static void main(String[] args) {
}
}
Prim算法调整
package com.zas.test.tree;
/**
* 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(minTree.isGraphHasCircle()){
minTree.removeEdge(edge);
}
}
}
return minTree;
}
/**
* 获取权重最小边
* @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(edge.isPointInEdge(p)){
if(e == null){
e = edge;
}else{
if(e.compareTo(edge) == -1){
e = edge;
}
}
}
}
}
return e;
}
/**
* @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);
}
}
Kruskal算法实现
package com.zas.test.tree;
import java.util.ArrayList;
import java.util.List;
/**
* Kruskal算法思想不同于Prim算法，
* Kruskal算法是一种按照连通网中边的权值的递增顺序构造最小生成树的算法。
* @author zas
*/
public class Kruskal {
//一个要找最小生成树的图
Graph graph;
public Kruskal() {
super();
}
public Kruskal(Graph graph) {
super();
this.graph = graph;
}
public Graph getGraph() {
return graph;
}
public void setGraph(Graph graph) {
this.graph = graph;
}
/**
* Kruskal算法的基本步骤 :
* 假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树。
* 令集合U的初值为U=V，即包含有G中全部顶点，集合TE的初值为TE={}。
* 然后，将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；
* 若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止，此时的T即为最小生成树。
* @return
*/
public Graph kruskal() {
Graph minTree = new Graph();
//将所有顶点加入最小生成树
for (Point p : this.getGraph().getPointList()) {
minTree.addPoint(p);
}
//对原图的边按权值从小到大排序
List<EdgeWithWeight> edgeList = sortByEdgeAsc(this.graph.getEdgeList());
//加入 n - 1条最小权值边
for (int i = 0; i < edgeList.size(); i++) {
EdgeWithWeight edge = edgeList.get(i);
minTree.addEdge(edge);
//是否含有环
if(minTree.isGraphHasCircle()){
minTree.removeEdge(edge);
}
//结束条件
if(minTree.getEdgeList().size() == minTree.getPointList().size() - 1){
break;
}
}
return minTree;
}
/**
* 对边按权值从小到大排序
* @param edgeList
* @return
*/
private List<EdgeWithWeight> sortByEdgeAsc(List<EdgeWithWeight> graphEdgeList) {
//克隆一下，防止影响到原图
List<EdgeWithWeight> edgeList = new ArrayList<EdgeWithWeight>();
for (EdgeWithWeight edgeWithWeight : graphEdgeList) {
edgeList.add(edgeWithWeight);
}
//暂时采用选择排序，如果数据规模大、有性能要求可改进
int selectedIndex = 0;
EdgeWithWeight edgeForSwap = null;
for (int i = 0; i < edgeList.size(); i++) {
selectedIndex = i;
for (int j = i + 1; j < edgeList.size(); j++) {
if(edgeList.get(j).compareTo(edgeList.get(selectedIndex)) == 1){
selectedIndex = j;
}
}
if(selectedIndex != i){
//交换
edgeForSwap = edgeList.get(selectedIndex);
edgeList.set(selectedIndex, edgeList.get(i));
edgeList.set(i, edgeForSwap);
}
}
return edgeList;
}
/**
* @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()));
Kruskal kruskal = new Kruskal(graph);
Graph minTree = kruskal.kruskal();
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)));
Kruskal kruskalForWeigtTree = new Kruskal(graphWithWeight);
Graph minTreeForWeightTree = kruskalForWeigtTree.kruskal();
System.out.println(minTreeForWeightTree);
}
}
测试用例所用的图
总结
Prim与Kruskal算法的关键都在于查找图是否含有环。
Prim算法从点入手，再加入与其有关的不产生环路的最小权重边。
Kruskal算法则先把所有点加入图，再加入n-1条不产生环路的最小权重边。
用面向对象的思维实现两个算法之后，感觉记忆更深刻了。
相关推荐
代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal...
编写算法能够建立带权图，并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树...
最小生成树Kruskal算法定义 本文将对最小生成树Kruskal算法进行详细的介绍和分析，并从技术角度对其进行剖析。 一、课程设计介绍 课程设计名称为“数据结构”，课程设计题目为“最小生成树Kruskal算法”，该课程...
### 最小生成树Kruskal算法详解 #### 算法背景与定义 最小生成树（Minimum Spanning Tree，简称MST）是图论中的一个经典问题，涉及到在一个加权图中寻找一棵包含所有顶点的子图，使得这棵子图的总权重最小。在实际...
实现了kruskal的算法，测试可行。
### 使用Prim和Kruskal算法构建最小生成树 在图论中，最小生成树（Minimum Spanning Tree, MST）是一个非常重要的概念。对于一个连通的无向图来说，如果存在一个子图，它包含原图的所有顶点，并且这些顶点通过边...
数据结构课程设计报告最小生成树Kruskal算法 数据结构课程设计报告中，我们将使用Kruskal算法来生成最小生成树，该算法是图论中的一种经典算法，能够在给定的图中找到最小生成树。下面，我们将对Kruskal算法的实现...
本文将详细介绍两种经典算法来解决最小生成树问题：Prim算法和Kruskal算法，并以C语言实现为例进行讲解。 ### Prim算法 Prim算法是一种贪心算法，其基本思想是从一个初始节点开始，逐步添加最短的边，直到连接到...
Kruskal算法是一种经典的求解最小生成树的方法，由Joseph Kruskal于1956年提出。该算法的主要思想是按照边的权重从小到大依次选择边，但要确保在添加新边时不会形成环路。具体步骤如下： 1. **边的排序**：首先，将...
Kruskal算法是一种求解最小生成树的经典算法，其核心思想是按边的权重从小到大进行选择，并在选择过程中避免形成环路，确保生成的树是连通的。 Kruskal算法的基本步骤如下： 1. 将图中的所有边按权重从小到大排序...
prim算法 Kruskal算法分别实现最小生成树
最小生成树（Kruskal 算法） 最小生成树是图论中的一种树结构，指的是连通图中的最小权值树。Kruskal 算法是最小生成树算法中的一种，用于寻找连通图中的最小生成树。 在 Kruskal 算法中，首先需要将图中的边按...
总结，Kruskal算法是一种有效的寻找图的最小生成树的方法，通过贪心策略避免环路并逐步构造出最小生成树。在C++中，利用排序和优先队列等数据结构，可以方便地实现这一算法。在实际应用中，Kruskal算法常用于解决如...
1. **引言**：介绍最小生成树的概念，以及Prim和Kruskal算法的基本思想。 2. **算法描述**：详细解释两种算法的步骤，包括伪代码或流程图。 3. **实现细节**：展示如何用编程语言（如C++、Java或Python）实现这两种...
该程序是我写的博客“一起talk C栗子吧（第五十回：C语言实例--最小生成树二）”的配套程序，共享给大家使用
对给定的图结构，实现求解最小生成树的Kruskal算法。每次在满足和已选边不构成回路的条件下选择一条权植最小的边，添加到新的生成数中。Kruskal算法的实现类似于计算连通枝的算法。它使用了分离集合数据结构以保持数...
"最小生成树(Kruskal算法)" 最小生成树是图论中的一种基本概念，指的是连通图中的一棵生成树，使得树中的每一条边的权值之和达到最小。Kruskal算法是构造最小生成树的一种常用方法，本文将对Kruskal算法进行详细的...
最小生成树kruskal算法并查集版 C语言实现 - Slyar Home