JAVA—咖啡馆

——欢迎访问rogerfan的博客,常来《JAVA——咖啡馆》坐坐,喝杯浓香的咖啡,彼此探讨一下JAVA技术,交流工作经验,分享JAVA带来的快乐!本网站部分转载文章,如果有版权问题请与我联系。

BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

【JAVA算法】

使用JAVA语言来实现算法。
     摘要: 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 阅读(1010) | 评论 (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 阅读(710) | 评论 (0)  编辑

     摘要: 当每个任务有前后置关系时,需要找到一种满足前后置关系的路线,将任务完成。

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

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

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

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

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

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

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

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

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

     摘要: 图中代权的最小树的问题如下:


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


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

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

算法简述如下:

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

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

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