zhuyufufu
- 浏览: 138843 次
- 性别:
- 来自: 南京
-
文章分类
最新评论
-
zheng_zhimeng：
这个版本在linux的版本下有问题，亲们用的没有问题么
文档展示：IcePDF 将PDF转换为图片 -
yuming.xiao：
转换的某些图片,有些模糊。不知道楼主遇到这个问题没有
文档展示：IcePDF 将PDF转换为图片 -
zenghongqing：
您好，请教您一个问题：//cell内容字符串总宽度 doub ...
Java POI Excel 行高自适应 -
xiang37：
http://xiva.iteye.com/blog/2066 ...
视频分割项目预研 -
I白I：
怎么还配置数据库了？
视频分割项目预研
最小生成树
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
最小生成树可参考：http://baike.baidu.com/view/288214.htm
下面实现最小生成树的Prim算法。
网上包括很多论坛里实现最小生成树的算法多为二维数组、面向过程的方式。最近得闲试着用Java代码实现面向对象的最小生成树算法。这样从实用角度看至少没那么书卷气了。
准备工作：
点、边、图的实现
点
普通边
权重
带权边
图
Prim算法
Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。
Java实现：
测试结果
边权重一样的图
边权重不一样的图
以上代码还有重构优化的余地，如：计算顶点的度，获取权重最小边可移入图类中；点是否在边中可移入边类中；图是否有环的代码看起来不够一目了然等。
另外最小生成树算法还有Kruskal算法；Dijkstra（迪杰斯特拉）算法也可以用来实现最小生成树程序。
以后有空再实现之。
参考资料：
可从下面链接找到我的测试用例所用的图，以及Prim算法的解释
http://squirrelrao.iteye.com/blog/1044867
可从下面链接找到无向图的环查找算法：
http://blog.csdn.net/sunmenggmail/article/details/7324646
一个有 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
踩
踩
分享到：
发表评论
-
oracle按照某一字段里的数字排序
2014-10-21 19:59 1089select * from LSK_SBCAJ t ord ... -
JS onkeydown onenter
2014-10-20 16:53 1004html中 onenter不是一个标准的事件。 js 中仿o ... -
Java数组删除指定元素
2014-09-18 11:30 2253package com.zas.util; impo ... -
sql 去重
2014-09-18 10:43 639delete from table t1 where t1.i ... -
linux 干掉所有java进程
2014-08-07 12:31 1033ps -ef|grep java|grep -v grep|c ... -
Oracle自带连接池使用(转载收录)
2014-07-31 10:01 1412最近在搞数据迁移：从sql server 迁数据到oracle ... -
html dom jsoup httpclient
2014-07-10 21:45 1114xml dom 对大多数java程序员来说并不陌生，但是htm ... -
Oracle 清库脚本
2014-07-08 22:40 1314清库脚本一份 表dossier_group 的字段Dossi ... -
Java 对象存储到oracle Blob字段
2014-07-08 14:52 1101Java 数据对象在没有持久存储到业务表时，可能需要临时存 ... -
Java 科学计数法数字转字符串
2014-07-08 14:30 1509科学计数法数字转字符串，记录代码，留后使用 double ... -
突破tomcat jsp编译65535行的限制
2014-07-04 17:16 4791使用tomcat时有可能会遇到其对jsp编译行数的限制， ... -
oracle 函数中游标及递归的应用
2014-06-19 17:13 1423在代码中使用递归可能大部分程序员都不陌生，但是在存储过程或 ... -
视频操作类
2014-06-19 17:04 1135接 视频分割项目预研 http://zhuyufufu.i ... -
视频分割项目预研
2014-06-11 16:12 2271由于工作需要，研究下视频切割。 现在的情况：视频切割是重中之 ... -
Java POI Excel 行高自适应
2014-03-28 14:08 15887在Excel处理的过程中，可能有需要用到行高自适应的时候。 ... -
Java POI Excel sheet 合并遇到的问题解决2
2014-03-25 18:03 3247上接 Java POI Excel sheet 合并 http ... -
文档展示：使用iText转换各种图片为PDF
2014-03-23 12:38 2907如题： 下面这段代码可以处理各种格式的图片，代码的出处忘记了 ... -
Java 进程执行外部程序，造成外部程序阻塞的一种原因
2014-03-23 12:06 1466前一阵子在研究文档展示时使用了java进程直接调用外部程序 ... -
Java POI Excel sheet 合并遇到的问题解决
2014-03-23 11:30 5123上接 Java POI Excel sheet http:// ... -
Java POI Excel sheet合并
2014-03-19 10:59 6628由于工作上的需要，特地研究了下Excel合并的问题，现贴出来， ...
相关推荐
Prim算法是求解最小生成树的一种经典算法，由Vojtěch Jarník、Karl Menger和Joseph Kruskal等人独立提出，但以Ernesto Prim的名字最为人所知。 Prim算法的基本思想是从图中任意一个节点开始，逐步添加边，使得...
在VC++环境下，实现遗传算法求解最小生成树，首先需要理解遗传算法的基本流程：初始化种群、选择、交叉、变异以及适应度计算。以下是对这个过程的详细说明： 1. 初始化种群：随机生成一组可能的解，每个解可以看作...
3. 最小生成树的生成：我们使用了一个名为MFSet的类来实现克鲁斯卡尔算法，该类中包括了两个主要函数：root函数用于查找元素的根节点，Tmerge函数用于合并两个集合。我们使用了一个名为main的函数来调用这些函数，...
在实现最小生成树算法时，C++提供了高效的数据结构（如数组、链表）和算法实现工具。 对于给定的描述，“输入顶点和权，显示邻接矩阵”意味着程序可能包含以下功能： 1. 用户输入：允许用户输入顶点的数量和它们...
最小生成树算法的目标是从一个加权无向图中找到一棵包括所有顶点的树，使得这棵树的所有边的权重之和尽可能小。这样的树被称为最小生成树。在实际应用中，这个概念广泛应用于电信网络规划、电路设计和运输路线规划等...
Java作为一种广泛使用的面向对象编程语言，具有丰富的类库和强大的跨平台能力，非常适合用于这样的算法实现。在实现过程中，可能会用到`java.util`包中的数据结构，如ArrayList或LinkedList来存储城市和边，以及优先...
在提供的压缩包文件“最小生成树”中，很可能包含了一个名为“最小生成树”的MATLAB源代码文件，这个文件应该实现了上述的Kruskal算法。通过阅读和理解这段代码，你可以深入学习Kruskal算法的细节，以及如何在MATLAB...
在介绍的文档中，主要讲解了如何用JavaScript（JS）实现两种著名的最小生成树算法：Prim算法和Kruskal算法。 ### Prim算法 Prim算法是由Vojtěch Jarník提出，后由Robert Prim推广的贪心算法，其核心思想是从图中...
基于最小生成树算法的南昌地铁票价查询C++代码(C++ code of Nanchang subway fare query based on minimum spanning tree algorithm)C++是一种广泛使用的编程语言，它是由Bjarne Stroustrup于1979年在新泽西州...
在Java中实现这些算法时，可以利用其丰富的数据结构（如数组、链表、队列、堆等）和面向对象的特性，使得代码更加清晰和高效。通过实践这些算法，不仅能加深对它们的理解，还能提升编程技巧，为解决更复杂的问题打下...
在实际应用中，如构建通信网络、设计高效的公路系统等，最小生成树算法有着广泛的应用。本项目是使用C++的MFC（Microsoft Foundation Classes）框架实现最小生成树的图形化表示，适合于数据结构学习者和编程爱好者...
1、最小生成树的概念； 2、Prim算法及其实现； 3、Kruskal算法及其实现； 4、图的表示； 5、边的表示； 6、优先队列priority_queue的自定义排序 7、大根堆、小根堆的区别 8、结构体的构建 面向对象： 有一定C++基础...
在提供的压缩包中，"最小生成树"可能是一个源代码文件或文档，详细解释了如何实现最小生成树的算法；"sure"可能是程序的可执行文件或者项目的配置文件。如果你正在学习这方面的知识，通过分析和运行这些文件，你将能...
最小生成树（Minimum Spanning Tree, MST）是图论中的一个重要概念，主要应用于网络设计、数据传输优化等领域。在这个场景中，我们提到的MST是用MFC（Microsoft Foundation Classes）编程实现的一个程序，用于解决...
在图论领域，寻找图的最小生成树是解决网络优化问题的关键之一。Chu-Liu/Edmonds算法，也被称为Kruskal's算法的一个变种，特别适用于寻找有向加权图的最小最大生成树。本文将深入探讨该算法的原理，并重点介绍由...
例如，霍夫曼编码和Prim最小生成树算法。 4. **回溯法**：在解决问题时尝试所有可能的解决方案，但一旦发现错误就回溯。如八皇后问题、数独等。 5. **分治策略**：将大问题分解为小问题来求解，如快速排序、归并...
- **图**：图的表示（邻接矩阵、邻接表），图的遍历（深度优先搜索、广度优先搜索），最小生成树（Prim算法、Kruskal算法）。 - **排序**：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等比较和实现...
除了基本算法，本书还可能涉及字符串处理、图形和几何算法、图论算法（如最短路径算法Dijkstra和最小生成树算法Prim）以及回溯法、贪心算法等。这些算法在实际问题中有着广泛的应用，例如网络路由、物流优化、游戏...
解决欧几里得最小生成树。 使用CMake作为构建工具。 src目录包含主项目的源代码。 测试目录包含测试代码。 testcase目录包含5个文件，这些文件是将在测试程序中使用的随机生成的测试数据。 在cmake中配置2个执行...