- 浏览: 1397727 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (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 入门讲解实例 转
图对建模很有帮助。
图的基本知识:
Java实现图的两种方法
1 邻接矩阵
邻接矩阵是用二维数据,使用1代表节点间有边,如下表格:
|
A |
B |
C |
D |
A |
0 |
1 |
1 |
1 |
B |
1 |
0 |
0 |
1 |
C |
1 |
0 |
0 |
0 |
D |
1 |
1 |
0 |
0 |
2 邻接表
临界表是使用类似链表,连接节点,表示有边
定点 |
包含邻接顶点的链表 |
A |
B->C->D |
B |
A->D |
C |
A |
D |
A->B |
深度遍历思路:
使用栈,查找栈顶顶点连通到的,没有访问的顶点,使其入栈,并访问。当找不到,则当前栈顶元素出栈。否则继续查找。
广度遍历思路:
使用队列,查找队列头连通的,没有访问的顶点,使其入队列,并访问。当找不到,则当前顶点出队列。否则继续遍历当前队列顶点
他们的不同之处就在,栈访问的顶点变化,会越来越深;队列访问的顶点不变化,只有出队列后才换节点访问。
图在java中的邻接矩阵实现:
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; // } } }
其中dfs是深度优先算法
bfs是广度优先算法
发表评论
-
java内存使用查看 转
2015-10-29 14:51 868转:http://mxsfengg.iteye.com ... -
Java线上应用故障排查之二:高内存占用
2015-08-17 16:28 0搞Java开发的,经常会碰到下面两种异常: 1、java. ... -
java filechannel
2015-08-14 15:42 1053Java NIO中的FileChannel是一个连接到文件 ... -
Java线上应用故障排查之一:高CPU占用
2015-08-06 13:58 6185转http://blog.csdn.net/blade20 ... -
java注释
2015-04-10 15:49 0Java注解是附加在代码中的一些元信息,用于一些工具在编译、 ... -
转jvm
2015-03-24 14:13 1672一、回顾JVM内存分配 ... -
java 域名转换
2014-12-22 11:05 767import java.net.InetAddres ... -
freemaker教程
2014-10-13 11:56 1980新换了工作,与想象差距也太大了 最近沦落到做报表了,我就 ... -
protocal buffers入门实例
2014-09-22 21:08 1654hadoop yarn中新的系列化protocol buf ... -
正则小计
2014-09-18 20:47 0&site=(.*?)&可以匹配site的值 ... -
在HBase中应用MemStore-Local Allocation Buffers解决Full GC问题
2014-06-13 23:05 1606译者注:上个月 ... -
java ipc 实例
2014-05-21 22:59 4877java ipc实例,仿照hadoop ipc写的实例 1 ... -
java worker thread模式
2014-03-25 22:46 1977转两个帖子 一个java wo ... -
bloom filter
2014-03-09 19:41 1954看到hadoop join和hbase都有bloo ... -
java reference
2014-03-09 17:49 716转 http://www.iteye.com/to ... -
annotation实例
2014-02-11 22:04 1140加载指定目录的所有class,通过注释区分实体类 p ... -
java获取子类 转
2014-02-11 16:58 3122获取子类 package com.tools; ... -
图论 五 最短路径 最长路径
2013-09-27 21:13 7434花几个算法的简易图: 一、 dijk ... -
动态代理
2013-08-14 20:38 1081动态代理,转:http://langyu.iteye. ... -
BTree B+Tree
2013-05-04 18:31 1964参考博文 http://blog.csdn.net/v_J ...
相关推荐
图的遍历是图论中的一个基础概念,用于探索图中的所有节点以及它们之间的连接关系。在计算机科学中,这通常用于数据结构的处理、网络路由、搜索算法等。本主题将详细介绍有向图和无向图的深度优先遍历(DFS)与宽度...
首先,我们来看看“图的深度广度遍历”。深度优先搜索(DFS, Depth First Search)和广度优先搜索(BFS, Breadth First Search)是图遍历的两种基本策略。 1. **深度优先搜索**:DFS是一种递归策略,它从图的一个...
本文主要探讨了在连通无向图上的两种遍历方法——深度优先搜索(DFS)和广度优先搜索(BFS),并结合C++编程语言进行了实践。 深度优先搜索通常使用栈来实现。在给定的概要设计中,ADT Stack被定义为具有初始化、...
本主题将深入探讨两种常见的图存储方式——邻接矩阵和邻接表,以及如何在这两种存储方式下实现深度优先遍历(DFS)和广度优先遍历(BFS)。 首先,邻接矩阵是一种直观的图表示方法,它使用二维数组来存储图中每个...
城市遍历求解问题在计算机科学中是一个经典的图论问题,通常被用来模拟旅行者试图以最有效的方式访问一系列城市。在这个Java课程设计项目中,我们可能会遇到如何使用编程技术来解决这一问题的挑战。这个问题可以被视...
本次课程设计的主题是“图的遍历和生成树求解实现”,这涵盖了两个核心概念:图的遍历算法(深度优先搜索DFS和广度优先搜索BFS)以及最小生成树(如Prim's算法或Kruskal's算法)。我们将深入探讨这两个知识点,并...
- **易于理解和实现**:相较于深度优先搜索,分层遍历更容易理解和编码。 - **良好的空间效率**:只需要额外的空间来存储当前层的节点,因此对于高度相对较小的树来说,空间复杂度较低。 - **方便获取各层节点数量**...
本资料包含关于图的深度优先遍历(DFS)和广度优先遍历(BFS)的实现代码,包括递归和非递归方式。下面将详细讲解这两种遍历方法。 1. 深度优先遍历(DFS) 深度优先遍历是从起点开始,尽可能深地探索图的分支。当...
在IT领域,图的遍历和最小生成树是图论中的两个重要概念,它们在算法设计和网络优化问题中有着广泛的应用。让我们深入探讨这两个概念。 首先,我们来看图的遍历。图是由顶点(节点)和边(连接顶点的线)构成的数据...
深度优先搜索(DFS, Depth-First Search)和广度优先搜索(BFS, Breadth-First Search)是图论中的两种基本搜索策略,用于遍历或搜索树或图。这两种算法在解决各种问题中有着广泛的应用,如路径查找、判断连通性、...
在计算机科学中,图是一种非常重要的数据结构,用于表示对象之间的关系。本资源包含了一些图算法的Java实现,包括但不限于广度...理解这些算法的原理和Java实现,对于提升编程能力,特别是解决图论问题的能力大有裨益。
图的遍历算法主要有深度优先搜索(Depth First Search, DFS)和广度优先搜索(Breadth First Search, BFS)两种。 ### 总结 本次实践操作涵盖了图论中的两个经典问题——最小生成树的求解和堆数据结构的应用。通过...
在编程中,有许多开源库支持图论算法,如C++的`Boost.Graph`库,Python的`NetworkX`,Java的`JUNG`等,这些库提供了丰富的接口和实现,简化了开发者在实际项目中应用图论算法的难度。 综上所述,“图论算法软件....
图论是计算机科学中的一个重要分支,它研究网络结构和关系,包括节点、边以及它们之间的连接。在有向图中,边是有方向的,从一个节点指向另一个节点,表示一种特定的流向。本主题主要关注如何在有向图中找到任意两点...
1. 深度优先搜索(DFS)和广度优先搜索(BFS):用于遍历和查找图中的特定路径或节点,帮助识别潜在的威胁路径。 2. 最小生成树算法(如Prim's和Kruskal's):用于构建网络的安全通信路径,减少攻击面。 3. 矩阵运算...
常见的图遍历方法有深度优先搜索(DFS,Depth-First Search)和广度优先搜索(BFS,Breadth-First Search)。 1. **深度优先搜索**:DFS是一种递归策略,从起始节点开始,尽可能深地探索图的分支,直到达到叶子节点...
3. **算法设计**:骑士游历的算法设计是关键,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历所有可能的路径。DFS通常用于寻找是否存在解,而BFS可以找到最短路径。骑士游历问题也可以转换成图论中的遍历...
在IT领域,图论是一种非常重要的理论基础,它在计算机科学和算法设计中扮演着核心角色。图论算法是解决复杂问题的有效工具,尤其在处理网络、数据结构和优化问题时。"suanfa.zip_图论_图论算法"这个压缩包文件很可能...
3. **遍历算法**:包括深度优先搜索(DFS)和广度优先搜索(BFS)。DFS适用于寻找路径或检测环,BFS常用于找到最短路径。 4. **最短路径算法**:Dijkstra算法用于找到单源最短路径,Floyd-Warshall算法用于求解所有...