- 浏览: 1381245 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (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 入门讲解实例 转
有向图的拓扑排序,能够获得访问到某一节点的提前条件。
拓扑排序时不可以实现环和图的拓扑排序。
写一下拓扑排序的实现:
是在联通矩阵上实现的,拓扑排序的算法是:
1.查看连通矩阵是否还有剩余节点,如果有继续2,3操作,如果没有结束拓扑排序
2.找到没有后继的节点
3.如果找到了,从联通矩阵中删除;如果没找到,则此联通矩阵不是DAG,不能进行拓扑排序
package com.Construction; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class GraphSimpleExample { private final int MAX_VERTS = 20; private GraphNodeBean nodeList[]; private int adjMat[][]; private int nVerts; public GraphSimpleExample(){ nodeList = new GraphNodeBean[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for (int i = 0; i < MAX_VERTS; i++) { for (int j = 0; j < MAX_VERTS; j++) { adjMat[i][j] = 0; } } } public void addNode(char label){ nodeList[nVerts++] = new GraphNodeBean(label); } public void addEdge(int start,int end){ adjMat[start][end] = 1; adjMat[end][start] = 1; } public void displayGraphNode(int v){ System.out.println(nodeList[v].label); } /** * 获得未访问节点 * @param v * @return */ public int getAdjUnvisitedVertex(int v){ for (int i = 0; i < nVerts; i++) { if(adjMat[v][i]==1 && nodeList[i].isVisited == false) return i; } return -1; } /** * deft first */ public void dfs(){ @SuppressWarnings("rawtypes") Stack<Integer> theStack = new Stack<Integer>(); nodeList[0].isVisited = true; displayGraphNode(0); theStack.push(0); while(!theStack.isEmpty()){ int v = getAdjUnvisitedVertex(theStack.peek()); if(v == -1) theStack.pop(); else{ nodeList[v].isVisited = true; displayGraphNode(v); theStack.push(v); } } // for (int i = 0; i < nVerts; i++) { // nodeList[i].isVisited = false; // } } public void bds(){ Queue<Integer> theQueue = new LinkedList<Integer>(); nodeList[0].isVisited = true; displayGraphNode(0); theQueue.offer(0); int v2; while(!theQueue.isEmpty()){ int v1 = theQueue.poll(); while((v2 = getAdjUnvisitedVertex(v1)) != -1){ nodeList[v2].isVisited = true; displayGraphNode(v2); theQueue.add(v2); } } // for (int i = 0; i < nVerts; i++) { // nodeList[i].isVisited = false; // } } /** * topologically output all the node 简单的拓扑排序 * 找到无后续节点,并输出,直到没有节点位置。 * 可以输出所有有顺序的关系,但是正确的输出不是唯一滴 * note: the graph only be DAG - including 不连通树, can't has cycles 环合树 */ public void topo(){ int orig_nVerts = nVerts; GraphNodeBean[] sortedArray = new GraphNodeBean[nVerts]; while(nVerts > 0){ int currentVertex = noSuccessor(); if(currentVertex == -1){ System.out.println("Error : Graph has cycles"); return; } sortedArray[nVerts - 1] = nodeList[currentVertex]; deleteVertex(currentVertex); } System.out.println("TOPOlogically sorted order:"); for (int i = 0; i < orig_nVerts; i++) { System.out.println(sortedArray[i].label); } } /** * within topology graph add a edge * @param start * @param end */ public void addTopoEdge(int start,int end){ adjMat[start][end] = 1; } /** * 找到没有后继的节点 * @return */ public int noSuccessor(){ boolean isEdge; for (int i = 0; i < nVerts; i++) { isEdge = false; for (int j = 0; j < nVerts; j++) { if(adjMat[i][j] > 0){ isEdge = true; break; } } if(!isEdge) return i; } return -1; } /** * delete certain node on the graph * @param delVert */ public void deleteVertex(int delVert){ if(delVert != nVerts - 1){ movingVertexData(delVert); for (int i = delVert; i < nVerts; i++) this.moveRowUp(i, nVerts); for (int i = delVert; i < nVerts; i++) this.moveColLeft(i, nVerts-1); } nVerts --; } /** * delete data from graph * @param index the number of data start with 0 */ public void movingVertexData(int index){ for (int i = index; i < nVerts -1; i++) { nodeList[i] = nodeList[i+1]; } } /** * row move up * @param row moving row number that start with 0 * @param length table column length */ public void moveRowUp(int row,int length){ for (int i = 0; i < length; i++) { adjMat[row][i] = adjMat[row+1][i]; } } /** * col move left * @param col moving column number that start with 0 * @param length table row lenglth; */ public void moveColLeft(int col,int length){ for (int i = 0; i < length; i++) { adjMat[i][col] = adjMat[i][col+1]; } } }
发表评论
-
java内存使用查看 转
2015-10-29 14:51 825转:http://mxsfengg.iteye.com ... -
Java线上应用故障排查之二:高内存占用
2015-08-17 16:28 0搞Java开发的,经常会碰到下面两种异常: 1、java. ... -
java filechannel
2015-08-14 15:42 1004Java NIO中的FileChannel是一个连接到文件 ... -
Java线上应用故障排查之一:高CPU占用
2015-08-06 13:58 6121转http://blog.csdn.net/blade20 ... -
java注释
2015-04-10 15:49 0Java注解是附加在代码中的一些元信息,用于一些工具在编译、 ... -
转jvm
2015-03-24 14:13 1638一、回顾JVM内存分配 ... -
java 域名转换
2014-12-22 11:05 734import java.net.InetAddres ... -
freemaker教程
2014-10-13 11:56 1908新换了工作,与想象差距也太大了 最近沦落到做报表了,我就 ... -
protocal buffers入门实例
2014-09-22 21:08 1601hadoop yarn中新的系列化protocol buf ... -
正则小计
2014-09-18 20:47 0&site=(.*?)&可以匹配site的值 ... -
在HBase中应用MemStore-Local Allocation Buffers解决Full GC问题
2014-06-13 23:05 1540译者注:上个月 ... -
java ipc 实例
2014-05-21 22:59 4832java ipc实例,仿照hadoop ipc写的实例 1 ... -
java worker thread模式
2014-03-25 22:46 1931转两个帖子 一个java wo ... -
bloom filter
2014-03-09 19:41 1922看到hadoop join和hbase都有bloo ... -
java reference
2014-03-09 17:49 687转 http://www.iteye.com/to ... -
annotation实例
2014-02-11 22:04 1100加载指定目录的所有class,通过注释区分实体类 p ... -
java获取子类 转
2014-02-11 16:58 3081获取子类 package com.tools; ... -
图论 五 最短路径 最长路径
2013-09-27 21:13 7364花几个算法的简易图: 一、 dijk ... -
动态代理
2013-08-14 20:38 1040动态代理,转:http://langyu.iteye. ... -
BTree B+Tree
2013-05-04 18:31 1915参考博文 http://blog.csdn.net/v_J ...
相关推荐
图论- AOV 网与拓扑排序.rar
数据结构课程的实验代码图论中的拓扑排序部分,有完整的可执行代码
科技论文——有向图所有基本回路的强核图论算法。。。。
拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键路径.pptx拓扑排序与关键...
阅读了《数据结构(C语言)》的经典著作后...本次算法课程设计运用所学的图论的拓扑排序和关键路径,去实现工程中的花费时间和顺利进行问题。拓扑排序主要用于检验工程能否施工,关键路径主要用于看出工程施工时间消耗。
声明:任何形式的转载请转载请保留出处保留出处 Wiki。
数据结构中的 ,狄克斯特拉(Dijkstra),弗洛伊德求最短路径的算法,和拓扑排序的算法,这里讲的十分的详述,而且还有模板语言实现。
JGraphT is a free Java class library that provides mathematical graph-theory objects and algorithms. JGraphT supports a rich gallery of graphs and is designed to be powerful, extensible, and easy to ...
根据邻接矩阵绘制图论图形。看注释使用,可以区分有向图和无向图
图的点表示活动有时有先后顺序执行,拓扑排序能有效解决这个问题
1. 有向图(Directed graphs) 2. 多图(Multigraphs) 3. 图生成器和图操作 1. 应用经典的图操作,例如: 2. 使用经典的小
拓扑排序课件 ,解答较为详细,对于拓扑排序、图论、BFS/DFS有较为详细的理解,适合入门一段时间的ACMer和想自学编程,研究学习算法者。
图论算法-求(有向)图中任意两点间所有路径
图论算法-二部图匹配图论算法-二部图匹配图论算法-二部图匹配
可以快速实现有向图的关联矩阵和邻接矩阵的转换
图论之二部图图形解析.doc
关于算法与图论中有向图的欧拉回路的判断,判断一个有向图是否有欧拉回路
基于矿床离散方法和单元块空间拓扑关系,以单元块为节点、块体开采净价值为节点权值,构建了带权初始有向图,进一步采用图论法求解最大闭包,获得了最优露天境界。为使初始有向图既满足最大允许边坡角要求,又避免冗余有...
图论算法-求(有向)图中任意两点间所有路径