JAVA—咖啡馆

——欢迎访问rogerfan的博客，常来《JAVA——咖啡馆》坐坐，喝杯浓香的咖啡，彼此探讨一下JAVA技术，交流工作经验，分享JAVA带来的快乐！本网站部分转载文章，如果有版权问题请与我联系。
BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

【JAVA算法】

使用JAVA语言来实现算法。
【转】通过分析 JDK 源代码研究 Hash 存储机制
     摘要: HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员，其中 HashMap 是 Map 接口的常用实现类，HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同，但它们底层的 Hash 存储机制完全一样，甚至 HashSet 本身就采用 HashMap 来实现的。
通过 HashMap、HashSet 的源代码分析其 Hash 存储机制

集合和引用

就像引用类型的数组一样，当我们把 Java 对象放入数组之时，并不是真正的把 Java 对象放入数组中，只是把对象的引用放入数组中，每个数组元素都是一个引用变量。


实际上，HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言，系统采用 Hash 算法决定集合元素的存储位置，这样可以保证能快速存、取集合元素；对于 HashMap 而言，系统 key-value 当成一个整体进行处理，系统总是根据 Hash 算法来计算 key-val  阅读全文
posted @ 2010-03-23 09:37 rogerfan 阅读(1021) | 评论 (0)  编辑

【转】图－最小树
     摘要: 如果一个图中所有点都是联通的，求最小树可以将图遍历完成，这里的最小是指边最少，跟边长没有关系。

算法利用深度优先遍历，记载每个遍历过的节点，将节点按照遍历顺序记录下来就是所谓的最小树。

关于深度优先遍历请参见深度优先遍历。

不过这里奇怪的是：

假如所有节点之间是双向联通的，只用生成一个数组，装入所有的节点，例如{'a','b','c','d','d'}

然后每两个点之间的线段就是最小树的结果，即a --> b, b --> c, c --> d, d --> e

似乎不用图这样复杂的结构支撑。

不过这里还是给出了按照图来产生最小树的办法。

Graph.mst：返回最小树。

Graph.main：提供简单测试。
  阅读全文
posted @ 2008-05-28 15:58 rogerfan 阅读(720) | 评论 (0)  编辑

【转】图－拓扑排序
     摘要: 当每个任务有前后置关系时，需要找到一种满足前后置关系的路线，将任务完成。

如果将每个任务看成一个节点，任务之间的前后置关系表示为有向图时，这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。

这里的图用邻接矩阵法表示，算法的关键是：

1 找到一个没有后继的顶点

2 在图中删除它，放入结果数组中

3 重复 步骤 1 ，步骤 2 直到图中没有多余的节点。

如果图中出现环装结构，则算法无法进行，因为此时任务之间循环成为前置。
  阅读全文
posted @ 2008-05-28 15:57 rogerfan 阅读(1127) | 评论 (0)  编辑

【转】图－传递闭包
     摘要: 图的传递闭包是指修正后的邻接矩阵表示的图。(见Graph 图－邻接矩阵法 )

在多个顶点的有向图中，每个顶点可以到按照方向到达一定的节点，这叫图的连通性。有种方法直接告诉我们，图中的两个节点是否可以联通，这里说的是WarShall算法。

WarShall的基本原理是，如果A可以到达B，且C可以到达A，则C可以到达B。通过对邻接矩阵的修正可以做到这点。随然这里举例是将两步可并成一步，但数学上可以证明这种修正可以达到任意步骤。
  阅读全文
posted @ 2008-05-28 15:54 rogerfan 阅读(931) | 评论 (0)  编辑

【转】图－每一对端点间的最小距离
     摘要: 与传递闭包问题 非常相似的一个问题是，能不能给出一个矩阵，根据矩阵可以以时间代价O(n)的方式得到在一个有向代权图中任意指定端点之间的最短距离。求的这个矩阵的问题被称为每一对端点间的最小距离问题。

这里采用的是Floyd算法，它与WalShall 算法非常相似：

如果A可以到达B，距离为x，且C可以到达A，距离为y，则求得C可以到达B，距离为 z = x + y，z小于如果c到B的原来的距离，则用z更新矩阵，否则c到B距离维持不变。

和最小路径算法类似，这里用一个很大数字INFINITY来表示两个端点之间距离为无穷大的情况，即不通。这里INFINITY＝最大的int值(~(1<<31))。

Floyd.main()提供简单的测试。

与WalShall 一样，Floyd算法本身的时间代价为O(n^3)
  阅读全文
posted @ 2008-05-28 15:53 rogerfan 阅读(394) | 评论 (0)  编辑

【转】图－代权最小树
     摘要: 图中代权的最小树的问题如下:


如果N个城市之间（图中的顶点）要修公路（图中的边）以使所有的城市联通，求怎样修可以使得公路的总长最小?
以上问题中的N个城市之间可以用图中的顶点表示，公路可以图中的边表示，公路的长度用边长表示，公路是双向的。问题就转换为在有N个顶点中的双向代权图中求得一个最小树。这里的代权指的边的长度，这与以前的不代权的最小树生成算法有很大的区别。


算法描述如下：
  阅读全文
posted @ 2008-05-28 15:45 rogerfan 阅读(409) | 评论 (0)  编辑

【转】图－最小路径
     摘要: 这里使用的是Dijkstra来计算最短路径。事实上Dijkstra完成时，指定节点到所有节点的最小路径均已求出。

算法简述如下：

准备好两个辅助性数据结构：

1 ParentLength ： 用来记录到当前节点之前的父节点，与到当前节点的最小路径

2 Path： 记录指定节点到所有节点的ParentLength。初始化时，所有的ParentLength的父节点都为指定的起始节点，长度都是INFINITY，代表没有联通，距离无穷大。
  阅读全文
posted @ 2008-05-28 15:39 rogerfan 阅读(875) | 评论 (0)  编辑