- 浏览: 1380533 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (346)
- linux (10)
- hbase (50)
- hadoop (23)
- java (52)
- java multi-thread (13)
- Oracle小记 (41)
- 机器学习 (12)
- 数据结构 (10)
- hadoop hive (16)
- java io (4)
- jms (1)
- web css (1)
- kafka (19)
- xml (2)
- j2ee (1)
- spring (6)
- ibatis (2)
- mysql (3)
- ext (3)
- lucene (3)
- hadoop pig (3)
- java nio (3)
- twemproxy (1)
- antlr (2)
- maven (6)
- mina (1)
- 列数据库 (1)
- oozie (2)
- mongodb (0)
- 报错 (0)
- jetty (1)
- neo4j (1)
- zookeeper (2)
- 数据挖掘 (3)
- jvm (1)
- 数据仓库 (4)
- shell (3)
- mahout (1)
- python (9)
- yarn (3)
- storm (6)
- scala (2)
- spark (5)
- tachyon (1)
最新评论
-
guokaiwhu:
赞啊!今晚遇到相同的问题,正追根溯源,就找到了博主!
hbase 报错gc wal.FSHLog: Error while AsyncSyncer sync, request close of hlog YouAr -
喁喁不止:
很清楚,有帮助。
hive常用函数 -
dsxwjhf:
Good job !!
kafka获得最新partition offset -
Locker.Xai:
参考了
freemaker教程 -
maoweiwer:
为啥EPHEMERAL_SEQUENTIAL类型的节点并没有自 ...
zookeeper 入门讲解实例 转
带权图是实际情况中经常使用的,如城市道路,etl优化等等。
在带权图中经常遇到的问题就是生成最小生成树,就是加权总值最小的路径,这里用prime算法实现
prim算法的总思路
/** * 生成最小生成树 * 将顶点放到树集合中,重复一下操作 * 1.找到最新的vertex到其他vertex的所有edge,其他vertex不能在树集合中,把这些edge放到优先队列中 * 2.找到权值最小的边,把edge和edge所到达的vertex放到树集合中 */
prim算法的过程示意图:这里贴一个邮电大学的
prim算法代码,java实现:
package com.Construction.DiscrectGraph; import java.io.ObjectOutputStream.PutField; public class Graph { /** * max vertx number */ private final int MAX_VERTX = 20; /** * max distance value */ private final int INFINITY = 1000000; /** * node list */ private Vertex vertexList[]; /** * adjacency matrix */ private int adjMat[][]; /** * graph node number */ private int nVerts; /** * prime tree number */ private int nTree; /** * current tree node */ private int currentVert; private PriorityQ priorityQueue; public Graph(){ vertexList = new Vertex[MAX_VERTX]; adjMat = new int[MAX_VERTX][MAX_VERTX]; nVerts = 0; for (int i = 0; i < MAX_VERTX; i++) { for (int j = 0; j < MAX_VERTX; j++) { adjMat[i][j] = INFINITY; } } priorityQueue = new PriorityQ(); } /** * 添加元素 * @param label */ public void addVertex(char label){ //添加元素,并将计数器加一 vertexList[nVerts++] = new Vertex(label); } /** * 添加边 * @param sv * @param dv * @param dis */ public void addEdge(int sv,int dv,int dis){ adjMat[sv][dv] = dis; adjMat[dv][sv] = dis; } /** * 生成最小生成树 * 将顶点放到树集合中,重复一下操作 * 1.找到最新的vertex到其他vertex的所有edge,其他vertex不能在树集合中,把这些edge放到优先队列中 * 2.找到权值最小的边,把edge和edge所到达的vertex放到树集合中 */ public void mstw(){ currentVert = 0; while (nTree < nVerts -1) { vertexList[currentVert].isInTree = true;//步骤2,放到树中 nTree ++; for (int i = 0; i < nVerts; i++) { if(i == currentVert) continue; // visit other graph node if(vertexList[i].isInTree) continue;//visit other graph don't contain in tree -- to avoid connect unneccessary node int dis = adjMat[currentVert][i]; if (dis == INFINITY) continue; putInPQ(i, dis); } if (priorityQueue.getSize() == 0) { return; } Edge currentMinEdge = priorityQueue.removeMin(); int sVert = currentMinEdge.srcVert; currentVert = currentMinEdge.destVert; System.out.println(vertexList[sVert].label); System.out.println(vertexList[currentVert].label); System.out.println(" "); } for (int i = 0; i < nVerts; i++) { vertexList[i].isInTree = false; } } /** * 将循环操作1中的edge,放入优先队列中 * 优先队列中,到一个目的的边是唯一滴,所有当已经有老边了,需要比较替代 * @param vertex * @param dis */ public void putInPQ(int vertex,int dis){ int index = priorityQueue.find(vertex); if(index != -1){ Edge tempEdge = priorityQueue.peek(index); int oldDis = tempEdge.distance; if(oldDis > dis){ priorityQueue.remove(index); Edge theEdge = new Edge(currentVert, vertex, dis); priorityQueue.insert(theEdge); } }else{ Edge theEdge = new Edge(currentVert, vertex, dis); priorityQueue.insert(theEdge); } } public static void main(String[] args){ Graph g = new Graph(); g.addVertex('A'); g.addVertex('B'); g.addVertex('C'); g.addVertex('D'); g.addVertex('E'); g.addVertex('F'); g.addEdge(0, 1, 6); g.addEdge(0, 3, 4); g.addEdge(1, 2, 10); g.addEdge(1, 3, 7); g.addEdge(1, 4, 7); g.addEdge(2, 3, 8); g.addEdge(2, 4, 5); g.addEdge(2, 5, 6); g.addEdge(3, 4, 12); g.addEdge(4, 5, 7); g.mstw(); } }
发表评论
-
java内存使用查看 转
2015-10-29 14:51 822转:http://mxsfengg.iteye.com ... -
Java线上应用故障排查之二:高内存占用
2015-08-17 16:28 0搞Java开发的,经常会碰到下面两种异常: 1、java. ... -
java filechannel
2015-08-14 15:42 1001Java NIO中的FileChannel是一个连接到文件 ... -
Java线上应用故障排查之一:高CPU占用
2015-08-06 13:58 6114转http://blog.csdn.net/blade20 ... -
java注释
2015-04-10 15:49 0Java注解是附加在代码中的一些元信息,用于一些工具在编译、 ... -
转jvm
2015-03-24 14:13 1636一、回顾JVM内存分配 ... -
java 域名转换
2014-12-22 11:05 732import java.net.InetAddres ... -
freemaker教程
2014-10-13 11:56 1897新换了工作,与想象差距也太大了 最近沦落到做报表了,我就 ... -
protocal buffers入门实例
2014-09-22 21:08 1599hadoop yarn中新的系列化protocol buf ... -
正则小计
2014-09-18 20:47 0&site=(.*?)&可以匹配site的值 ... -
在HBase中应用MemStore-Local Allocation Buffers解决Full GC问题
2014-06-13 23:05 1537译者注:上个月 ... -
java ipc 实例
2014-05-21 22:59 4830java ipc实例,仿照hadoop ipc写的实例 1 ... -
java worker thread模式
2014-03-25 22:46 1929转两个帖子 一个java wo ... -
bloom filter
2014-03-09 19:41 1918看到hadoop join和hbase都有bloo ... -
java reference
2014-03-09 17:49 684转 http://www.iteye.com/to ... -
annotation实例
2014-02-11 22:04 1097加载指定目录的所有class,通过注释区分实体类 p ... -
java获取子类 转
2014-02-11 16:58 3079获取子类 package com.tools; ... -
图论 五 最短路径 最长路径
2013-09-27 21:13 7363花几个算法的简易图: 一、 dijk ... -
动态代理
2013-08-14 20:38 1038动态代理,转:http://langyu.iteye. ... -
BTree B+Tree
2013-05-04 18:31 1913参考博文 http://blog.csdn.net/v_J ...
相关推荐
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
Prim算法是最小生成树一般算法的特例, Prim算法的特点是集合A的边总是只形成单棵树.
本程序是使用c++编写的prim最小生成树算法,需要输入的是graph的阶数以及边赋权图矩阵
Prim 算法求最小生成树 语法:prim(Graph G,int vcount,int father[]); 参数: G:图,用邻接矩阵表示 vcount:表示图的顶点个数 father[]:用来记录每个节点的父节点 返回值:null 注意: 常数max_vertexes 为图...
针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的min-reduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法...
洛谷原模板题p3366 题目网址: https://www.luogu.com.cn/problem/P3366
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为...
主要讲解了普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树,需要的朋友可以参考下
这是用prim算法实现的最小生成树算法,实质上是一个贪心算法的应用,看一下,会对你有帮助
该程序用C实现了最小生成树的prim和kruscal算法,并且也实现了,图的广度遍历和深度遍历,采用了临界矩阵或者是临界表的存储结构。
matlab算法,可以解决最小生成树算法以及类似问题关于最小生成树,学过图论的都懂,这里就不做介绍。 下面是一个例题,附有Kruskal算法和Prim算法。
图论算法(matlab),包含迪克斯特拉算法、图论弗洛伊德算法、最小生成树prim算法。亲自验证无误,可直接使用.
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为...
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为...
图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由...
2.2 Kruskal算法和Prim算法 3 单源最短路径 3.1 Bellman-Ford算法 3.2 有向无环图(DAG图)中单源最短路径问题 3.3 Dijkstra算法 3.4 差分约束和最短路径 3.5 最短路径的性质证明(三上无路收钱) 4 所有结点对的...
图论算法库 C++ 语言实现 代码内容 图论算法库,包括以下算法: 单源最短路径 Dijkstra 算法 单源最短路径 Bellman-Ford 算法 最小生成树 Prim 算法 每对节点间最短路径 Flod-Warshall 算法
Prim,Floyd,Dijkstra算法
最小生成树(prim+mapped_heap邻接表形式) 最小生成树(prim+mapped_heap正向表形式) 最小树形图(邻接阵形式) 应用\ joseph模拟 N皇后构造解 布尔母函数 第k元素 幻方构造 模式匹配(kmp) 逆序对数 字符串...