- 浏览: 3508205 次
- 性别:
- 来自: 杭州
文章分类
- 全部博客 (1491)
- Hibernate (28)
- spring (37)
- struts2 (19)
- jsp (12)
- servlet (2)
- mysql (24)
- tomcat (3)
- weblogic (1)
- ajax (36)
- jquery (47)
- html (43)
- JS (32)
- ibatis (0)
- DWR (3)
- EXTJS (43)
- Linux (15)
- Maven (3)
- python (8)
- 其他 (8)
- JAVASE (6)
- java javase string (0)
- JAVA 语法 (3)
- juddiv3 (15)
- Mule (1)
- jquery easyui (2)
- mule esb (1)
- java (644)
- log4j (4)
- weka (12)
- android (257)
- web services (4)
- PHP (1)
- 算法 (18)
- 数据结构 算法 (7)
- 数据挖掘 (4)
- 期刊 (6)
- 面试 (5)
- C++ (1)
- 论文 (10)
- 工作 (1)
- 数据结构 (6)
- JAVA配置 (1)
- JAVA垃圾回收 (2)
- SVM (13)
- web st (1)
- jvm (7)
- weka libsvm (1)
- weka屈伟 (1)
- job (2)
- 排序 算法 面试 (3)
- spss (2)
- 搜索引擎 (6)
- java 爬虫 (6)
- 分布式 (1)
- data ming (1)
- eclipse (6)
- 正则表达式 (1)
- 分词器 (2)
- 张孝祥 (1)
- solr (3)
- nutch (1)
- 爬虫 (4)
- lucene (3)
- 狗日的腾讯 (1)
- 我的收藏网址 (13)
- 网络 (1)
- java 数据结构 (22)
- ACM (7)
- jboss (0)
- 大纸 (10)
- maven2 (0)
- elipse (0)
- SVN使用 (2)
- office (1)
- .net (14)
- extjs4 (2)
- zhaopin (0)
- C (2)
- spring mvc (5)
- JPA (9)
- iphone (3)
- css (3)
- 前端框架 (2)
- jui (1)
- dwz (1)
- joomla (1)
- im (1)
- web (2)
- 1 (0)
- 移动UI (1)
- java (1)
- jsoup (1)
- 管理模板 (2)
- javajava (1)
- kali (7)
- 单片机 (1)
- 嵌入式 (1)
- mybatis (2)
- layui (7)
- asp (12)
- asp.net (1)
- sql (1)
- c# (4)
- andorid (1)
- 地价 (1)
- yihuo (1)
- oracle (1)
最新评论
-
endual:
https://blog.csdn.net/chenxbxh2 ...
IE6 bug -
ice86rain:
你好,ES跑起来了吗?我的在tomcat启动时卡在这里Hibe ...
ES架构技术介绍 -
TopLongMan:
...
java public ,protect,friendly,private的方法权限(转) -
贝塔ZQ:
java实现操作word中的表格内容,用插件实现的话,可以试试 ...
java 读取 doc poi读取word中的表格(转) -
ysj570440569:
Maven多模块spring + springMVC + JP ...
Spring+SpringMVC+JPA
1.大理论的一些资料
带权图
带权是说的是在图的连接边是有长度。我们来模拟这个环境:
中国的20个城市,每个城市好比一个图的顶点,火车在地面上开,有火车的轨道将20个城市连接在一起了
而火车的轨道好比是边,而轨道连接各个城市之间的的有长度的,那么这就形成了一个图----有火车的轨道网络,
这个例子说的就是带权的图了。
当把权值当做边的特性的时候,一些有趣的并且复杂的问题就出现了,
什么是带权的最小生成树?
什么是两个顶点间的最短距离?
这两个问题都在现实的生活中有非常大的意义的
2.小理论的一些资料(重要概念)
带权图的最小生成树
我们先来看普通的最小生成树。在有向图中创建一个树比在无向图中要复杂哦。当所有的边拥有相同的权值,问题就变的简单了,
算法可以任意选择一条边加入最小生成树。但是当边具有不同的权值时,需要用一些算法策略来选择正确的边。
一个实例:丛林中的有线电视
假设要再一个虚拟的国家M的6个城市之间架设有线电视网络,把它们都连接起来。五条边可以连接6个点,但是要怎么连接五条边呢
才能让线路最短。
步骤1.
随便 找一个顶点A,作为办公地点
步骤2.
找出各个直接与A连接的点,并且比较出最小的那条边。连接这条边的点就作为第二办公地点B,并且将这边架设好
步骤3.
规则1 已经架设好的边不修改
规则2 新建的办公地点开始办公,步骤类似于步骤2,并且将步骤2中遗留下来的边的长度一起比较,选择出最短的那条作为下一个办公点
步骤4
直到没有边或者全部连接好了顶点了,那么就停止了 ,连接线就是最短的线了。(其实表示还是不详细哦)
三类顶点
1.已经有办事处并且用电缆连接的城市,他们是最小生成树的顶点
2.还没有连接,也没有办事处的城市,但是知道了他们连接到至少有一个已经有办事处的城市电缆的安装造价了。
这些城市就叫做边缘城市
3还不知道任何信息的城市的
随着算法的进行,城市虫第三类到第二类到第一类
设计算法:
优先级队列
正如前面例子描述的那样,执行算法的关键行为是保存两个城市建立连接的造价单。通过选择造价最低的项,就可以决定下一条建在何处
建议用优先级队列来实现这个用于反复选择最小造价价值的表,而不用链表或者数组。这是解决最小生成树的有效方式。在正式的程序中,
优先级队列可能基于堆来实现。这加快了加大的优先级队列的操作,然而,在实例中,将用数组实现的队列进行优先级队列。
算法要点
下面用图的术语,重申下算法:
从一个顶点开始,把它放入树的集合中,然后重复做下面的事情:
1.找到最新的顶点到其他顶点的所以边,这些顶点不能在树的集合中,把这些边放入优先级队列中
2.找出权值最小的边,把它和塔所到达的顶点放入树 的结合中。
重复这些步骤,直到所以项目的顶点都在树的集合中了。这是工作就结束了。
在步骤1,最新的意味着最近放入树中的。此步骤的边可以在邻接矩阵中找到,步骤1完成后,表中包含了所有的边,这些边都是从树中顶点
到它们的不在树中的邻接点的连接
无用边
在表剩余条目中,想要把某些连接删除比较困难,它们都是从当前城市到已经拥有办事处的城市的连接,但是如果不做这个工作,就可能会导致
安装不必要的优先电缆
在程序的算法中,也要确保优先级队列中不能有连接已在书中的顶点的边,每次向树中增加顶点后,都要遍历优先级队列查找并删除这样的边,
这样做以后,要使优先队列中任意时刻只保存一条树中顶点到某边缘点的边就变得容易了,也就是说,优先级队列中应该包含一条到达
某个第二类顶点的边
部分代码
package endual;
public class ValueGraph { /** * 有权图的最小生成树的方法mstw() */ public void mstw() { currentVert = 0 ; //选择从开始点出发 /** * 算法中while中执行,循环结束条件是所以顶点都在书中了,循环中完成下面的操作 * 1.当前的顶点放入到树中去,从第一个开始 * 2.连接这个顶点的边全部放入到优先级队列中(如果合适) * 3.从优先级队列中删除权值最小的边。这条边的目的顶点变成当前顶点 * * 在看看这些步骤的细节、 * 在步骤1中,通过标记currentVert所指顶点的isInTree字段来表示该顶点放入树中 * 在步骤2中,连接这个顶点的边插入优先级队列。通过在连接矩阵中扫描号是currentVert的 * 行寻找需要的边。只要下面任意的一个条件为真,那么这条边就不能放入到队列中 * * 1.源点和终点是相同的 * 2.原点在树中了(重点看下这个概念) * 3.源点和终点之间没有边(链接矩阵中对于的值等于无限大) * * 如果没有一个条件为真,调用putInPQ()方法把这条边放入到这个优先队列中。实际上,正如下面要到的,这个列程并不总是把 * 边放入到优先队列中去的 * * 在步骤三种,将最小权值的边从优先级队列中删掉,把这条边和该边的终点加入树,并显示原点和终点 * * 最后的for循环将数据复原 * * * */ while (nTree < nVerts-1) { //顶点的数大于树的数 vertexList[currentVert].isInTree = true ; //已经放入到树中了 nTree++ ; //树中的数目加一个 //insert edges adjacent to currentVert into Pq for (int j=0; j<nVerts; j++) { if (j == currentVert) { continue ; } if (vertexList[j].isInTree) { continue; } int distance = adjMat[currentVert][j] ; if (distance == INFINITY) { //skip if no edg 如果没有边,那么就跳过 continue ; } putInPQ(j,distance) ; //放入到优先队列中去 } //end for if (thePQ.size()==0) { System.out.println("GPAPH NOT CONNECTED") ; return ; } //remove edge with mini distance , from PQ Edge the Edge = thePQ.removeMin() ; //将最小的边移除掉 int sourceVert = theEdge.srcVert ; correntVert = theEdge.destVert ; //displayedge for source to current System.out.println(vertexList[sourceVert].label) ; System.out.println(VertextList[currentVert].label) ; System.out.println(" ") ; } // end while // mst is complete for (int j=0; j<nVerts; j++) { verttexlist[j].inInTree = false ; //没有被放入到最小生成树中 } } }
全部代码
首先我们创建边了
package endual; public class Edge { public int srcVert ; //一个顶点开始的序列好 public int destVert ; //一个顶点结束的序号 public int distance ;//从开始到介绍的长度 public Edge(int srcVert, int destVert, int distance) { super(); this.srcVert = srcVert; this.destVert = destVert; this.distance = distance; } }
然后我们创建顶点了
package endual; public class Vertex { private char label; // 顶点的标记 private boolean isInTree; // 是否在最小生成树中了 private boolean isVisited; // 是否已经被访问 public Vertex(char label) { super(); this.label = label; this.isInTree = false; this.isVisited = false; } public char getLabel() { return label; } public void setLabel(char label) { this.label = label; } public boolean isInTree() { return isInTree; } public void setInTree(boolean isInTree) { this.isInTree = isInTree; } public boolean isVisited() { return isVisited; } public void setVisited(boolean isVisited) { this.isVisited = isVisited; } }
我们创建优先队列 是基于数组的哦
package endual;
public class PriorityQ {
private final int SIZE = 20;
private Edge[] queArray;
private int size;
public PriorityQ() {
super();
this.queArray = new Edge[this.SIZE];
this.size = 0; // 当前队列中的数目
}
// 插入边长
public void insert(Edge item) {
int j;
for (j = 0; j < this.size; j++) {
if (item.distance > this.queArray[j].distance) {
break;
} // 如果当前插入的边长当前的节点长度大,那么就停止掉,寻找到数组中的位子
// 因为现在数组的位子是有人的,那么就以为,把这个位子空出来
for (int k = this.size - 1; k >= j; k--) {
this.queArray[k + 1] = this.queArray[k];
}
// 空出来的位子就插入进去
this.queArray[j] = item;
size++; // 当前队列中的数要增加一个
}
} // end
// 移除最小的那个边
public Edge removeMin() {
this.size = this.size - 1;
return this.queArray[this.size];
}
public void removeN(int n) { //移除在数组中为是n的数据
for (int j=n; j<size-1; j++) {
this.queArray[j] = this.queArray[j+1] ;
}
this.size-- ;
}
public Edge peekMin() { //只是查看并没有删除
//this.size =
return this.queArray[this.size - 1];
}
public Edge peelN(int n) { //n从0开始的
return this.queArray[n] ;
}
//当前的数目
public int size() { //当前的数目呢
return this.size ;
}
//是否为空
public boolean isEmply() {
if (this.size != 0) {
return false ;
}
return true ;
}
//是否为满
public boolean isFull(){
if (this.size == this.SIZE) {
return true ;
}
return false ;
}
//找到一个序号
public int find(int findDex) { //找到特殊的边
for (int j=0; j < this.size; j++) {
if (this.queArray[j].destVert == findDex) {
return j ;
}
}
return -1 ;
}
} // end class
然后我们创建图了,在图中创建方法
package endual;
public class Graph {
private final int MAX_SIZE = 20;
private Vertex[] vertexList;
private final int INFINITY = 10000000; // 认为是这个无限大的,测试两个点之间的距离是不是之间相连的
private int adjMat[][]; // 存放在顶点是不是连接点,也就是也矩阵的方式进行存放
private int nVerts; // 当前图中的数量
private int currentVert;
private PriorityQ thePQ;
private int nTree; // 当前树的长度
public Graph() {
super();
this.vertexList = new Vertex[this.MAX_SIZE];
this.adjMat = new int[19][19];
this.initialAdjMat();
this.nVerts = 0;
this.currentVert = 0;
this.thePQ = new PriorityQ();
this.nTree = 0;
}
private void initialAdjMat() {
for (int i = 0; i < this.MAX_SIZE; i++) {
for (int j = 0; j < this.MAX_SIZE; j++) {
this.adjMat[i][j] = INFINITY; // 顶点之间是无线的长的
}
}
}
// 向图中插入顶点
public void insertVertex(char a) {
Vertex v = new Vertex(a);
this.vertexList[this.nVerts] = v;
this.nVerts++;
}
// 插入带全的边
public void addEdge(int start, int end, int weight) {
this.adjMat[start][end] = weight;
this.adjMat[end][start] = weight;
}
// 显示顶点
public void displayVertex(int v) {
System.out.println(vertexList[v].getLabel());
}
// 带权图的最小生成树方法
public void mstw() {
this.currentVert = 0;// 从第一个顶点开始取,就是在数组中保存的第一个顶点开始的
while (this.nTree < this.nVerts - 1) {
this.vertexList[this.currentVert].setInTree(true); // 当前节点放入到tree中,其实这个是数组形状的最小生成树
this.nTree++; // 那么当前的树要增加一个了
// 将和当前顶点连接的顶点的边长放入到优先队列中去
for (int i = 0; i < this.nVerts; i++) {
if (i == this.currentVert) { // 当前节点是自身本身的话,那么就跳出,寻找下一个
continue;
}
if (this.vertexList[i].isInTree() == true) { // 当前节点以及在树中了,也跳出循环寻找下一个
continue;
}
int dis = this.adjMat[this.currentVert][i];
if (dis == this.INFINITY) { // 当前节点与节点i直接的距离是无线大,所以没有连接的
continue;
}
// 那么当前节点与连接的顶点就是dis了
putInPQ(i, dis); //多次循环,将优先队列中是否有相同长度的老边给代替掉
} //end for
if (thePQ.size() == 0) { //如果队列中的长度是0那么就说没有点了
System.out.println("graph not connected") ; //该图是一个没有边连接的图
}
//现在就显示
//优先队列中移除最小的树的边,来生成我们要用的最小的生成树
Edge minEdge = thePQ.removeMin() ;
int sourceVert = minEdge.srcVert ;//开始的点
this.currentVert = minEdge.destVert ; //当前节点
System.out.println(this.vertexList[sourceVert].getLabel()) ;
System.out.println(this.vertexList[currentVert].getLabel()) ;
System.out.println(" ") ;
} // 当图中的顶点都没有的时候就跳出循环
//复原我们的初始顶点
initialGraph() ;
}
private void initialGraph() {
for(int j=0; j < this.nVerts; j++) {
this.vertexList[j].setInTree(false) ;
}
}
private void putInPQ(int i, int dis) {
//is there another edge with the same destination vertex ?
//是否存在另一条边的长度和新的边的长度是一样的顶点
int queueIndex = thePQ.find(dis) ; //寻找到一个距离
if (queueIndex != -1) { //如果那么是不等于,没有的话是返回-1
Edge tempEdge = thePQ.peelN(queueIndex) ; //找到这个边
int oldDist = tempEdge.distance ; //边的长度是多少,该边的长度
if (oldDist > dis) {
//如果老边的长度是大于新边的长度的话
thePQ.removeN(queueIndex) ; //移除这个老的节点
Edge theEdge = new Edge(this.currentVert,i, dis) ;//创建一个新的边
thePQ.insert(theEdge) ; //插入到新的队列中
}
else {//如果没有这样的边
Edge theEdge = new Edge(this.currentVert,i, dis) ;//创建一个新的边
thePQ.insert(theEdge) ; //插入到新的队列中
}
}
}
}
发表评论
-
java 归并排序 自己写
2012-02-22 09:03 1424package endual.xier.writeaga ... -
递归思想 汉诺塔的问题
2012-02-09 10:46 1606package endual; public cl ... -
带权图 最短路径 代码自己写
2012-02-09 10:46 3142最短路径问题 可 ... -
数据结构学习的在线好网址
2012-02-07 16:20 1518http://sjjg.js.zwu.edu.cn/SFXX/ ... -
有向无环图 拓扑排序
2012-02-07 15:53 3418package endual.tuopupaixu; ... -
java 图的最小生成树问题 (代码自己写)
2012-02-07 13:51 2752最小生成树是基于无无向图,并且是没有权值的图的。它的实现可以用 ... -
java 图 代码自己写
2012-02-07 13:07 1757图的建立也是基于数组的,但是遍历的话是基于链表或者是矩阵的 ... -
堆 (自己写)
2012-02-06 13:32 1430堆也是基于数组的哦,所以在创建的时候,请先要考虑好数组的大小了 ... -
哈希表的一些概念 代码(自己写)
2012-02-05 18:44 2121首先,我们要明确一点 ... -
红黑树的一些概念
2012-02-05 14:43 1981普通的二叉树作为数 ... -
两个正整数相加
2012-02-05 09:48 1839import java.util.Scanner; i ... -
二叉树代码
2012-02-05 09:51 1669package endual; /** * 树 ... -
java 二叉树
2012-02-04 14:17 1541为什么要用二叉树 通常我们去实现数据结构有两种方式,一 ... -
桶排序(代码自己写)
2012-02-04 13:24 1985简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶 ... -
各类排序算法
2012-02-04 13:19 1446隐藏▲ 查 · 论 -
快速排序算法(自己写)
2012-02-04 12:58 1720快速排序算法的伪代码。 package endual; ... -
java 希尔排序算法(自己写)
2012-02-04 10:26 1809希尔排序算法是对插入算法的应用吧,就是多次的使用了插入算法多排 ... -
递归 字符串的全排列
2012-02-03 15:29 2427package endual; public class ... -
java递归的一个问题
2012-02-03 13:56 1840据说比达格斯理论家,又称一群在必达格斯领导下工作的古希腊数学家 ... -
java 实现链表(自己写的)
2012-02-03 11:03 1621今天用java写了下的链表, 还是有点糊涂的。这和C语言写的链 ...
相关推荐
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
我们的一个计算机软件基础大作业是编写4个程序,分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较,最后交一个报告,所以花了很长时间写了这边报告,既完成任务,也是对自己编写程序的...
用普里姆(Prim)算法构造最小生成树 数据结构树与图的经典编程题。优秀的代码哦。
最小生成树的代码表现方法,构造带权无向图G6的最小生成树。构造带权无向图的最小生成树。
最小生成树(Prim,Kruskal)C++代码实现 (可运行,含测试用例,有输出,注释详细) 对于一个带权连通图,生成树不同,树中各边上权值总和也不同,权值总和最小的生成树则称为图的最小生成树。
本项目实现了无向图的连通性判定和利用无向连通带权图构造最小生成树的算法。此项目源码在Win7(64位)平台下VS2010环境中可成功运行。请大家批评、指正。
Prim算法能够在带权的图中搜索出最小生成树,这也是各大ACM和面试及考研题目中的热点,下面我们就来详细看一下Prim(普里姆)算法求最小生成树的思想及C语言实例讲解
最小有向最大生成树作者:DirectedMinimalSpanningTree.m 3.最大有向最大生成森林作者:MaximalDirectedMSF.m 4. 最小有向最大生成森林由 MinimalDirectedMSF.m 可以从“ControlCenter.m”开始,这里是一个简单的...
本人是南京航空航天大学的学生,我们的一个计算机软件基础大作业是编写4个程序,分别是约瑟夫斯问题、停车场管理、带权图的最小生成树提取、几种排序算法的比较。希望能够帮助到大家,尤其是南航的学弟学妹们!工程...
附送Kruskal最小生成树算法,都是本人的劳动成果,包含输入输出的完整控制台程序,希望大家下完顶一下:)
普里姆算法在找最小生成树时,将顶点分为两类,一类是在查找的过程中已经包含在树中的(假设为 A 类),剩下的是另一类(假设为 ...所走过的顶点和边就是该连通图的最小生成树。 PS:运行代码在我的博客找对应的文章即可
离散数学实验(南京航空航天大学) 对于n阶完全带权图,使用以下两种算法获得TSP问题的近似解,并对所得结果进行比较: 1.最邻近法 2.最小生成树法
" "(4)掌握图的其他运算 ,包括最小生成树,最短路径,拓扑排序和关键路径等算法。" "(5)灵活运用图这种数据结构解决一些综合应用问题。 " "二、实验内容和方法 " "(1)实验内容: " "1、编写一个程序algo8-1....
--------普里姆最小代价生成树算法-------- ---4 -------用邻接矩阵构造带权有向图-------- --------------最短路径--------------- --------用邻接表构造有向图--------- b c d e e d e ---------初始时各个顶点的...
分别对有向图、无向图、带权有向图、带权无向图实现对图的基本操作(创建、求顶点的度数、增加/删除边、判断边是否存在、DFS、...代码中还实现了顶点的增删、图的保存与再生、最小生成树、最短路径、所有路径的可视化。
带权图的最小生成树 最短路径问题 每一对顶点之间的最短路径问题 效率 难题 小结 问题 实验 编程作业 第15章 应用场合 通过数据结构 专用数据结构 排序 图 外部存储 前进 附录A 运行专题applet和...
带权图的最小生成树 最短路径问题 每一对顶点之间的最短路径问题 效率 难题 小结 问题 实验 编程作业 第15章 应用场合 通过数据结构 专用数据结构 排序 图 外部存储 前进 附录A 运行专题applet和...
上溯时走左分支则生成代码 0 ,走右分支则生成代码 1 。重复上述过程直到编码所有的叶子结点。 Huffman译码算法 译码是编码的逆运算。译码过程是根据构建的Huffman树和相应的Huffman编码,从H树的根出发,逐个读取...
哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树,广泛应用于数据压缩和编码领域。这个资料包提供了一种基于链表实现的哈夫曼树构建方法,相较于其他实现方式,链表结构更加紧凑,内存占用较小,且易于...
8.8 最小生成树(kruskal) 172 8.9 最短路径 173 8.10 最大网络流 175 8.11 最小费用流 180 8.12 最大团问题 182 8.13 二分图匹配 184 8.14 带权的最优二分图匹配 184 9.搜索算法概略 187 9.1 迭代深搜+IDA* 187 9.2 ...