Core Java 2 Volume I - Fundamentals, Seventh Edition.pdf
Core Java 2 Volume II - Advanced Features, Seventh Edition.pdf
- 00:33
- 浏览 (12)
- 评论 (0)
这里使用的是Dijkstra来计算最短路径。事实上Dijkstra完成时，指定节点到所有节点的最小路径均已求出。
算法简述如下：
准备好两个辅助性数据结构：
1 ParentLength ： 用来记录到当前节点之前的父节点，与到当前节点的最小路径
2 Path： 记录指定节点到所有节点的ParentLength。初始化时，所有的ParentLength的父节点都为指定的起始节点，长度都是INFINITY，代表没有联通，距离无穷大。
Path的关键算法是adjust(from,to,length)，每当发现一条新的，从一个已访问的节点（from）到未访问的节点（to）之间的新路径时，P ...
图中代权的最小树的问题如下:
如果N个城市之间（图中的顶点）要修公路（图中的边）以使所有的城市联通，求怎样修可以使得公路的总长最小?
以上问题中的N个城市之间可以用图中的顶点表示，公路可以图中的边表示，公路的长度用边长表示，公路是双向的。问题就转换为在有N个顶点中的双向代权图中求得一个最小树。这里的代权指的边的长度，这与以前的不代权的最小树生成算法有很大的区别。
算法描述如下：
任选一个节点开始，将该节点标志为已访问过的节点。也就是最小树中的节点。并设置为当前节点。
1 寻找此访问节点的所有的邻接 ...
与传递闭包问题
非常相似的一个问题是，能不能给出一个矩阵，根据矩阵可以以时间代价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< ...
图的传递闭包是指修正后的邻接矩阵表示的图。(见Graph 图－邻接矩阵法
)
在多个顶点的有向图中，每个顶点可以到按照方向到达一定的节点，这叫图的连通性。有种方法直接告诉我们，图中的两个节点是否可以联通，这里说的是WarShall算法。
WarShall的基本原理是，如果A可以到达B，且C可以到达A，则C可以到达B。通过对邻接矩阵的修正可以做到这点。随然这里举例是将两步可并成一步，但数学上可以证明这种修正可以达到任意步骤。
下面是代码：
class WarShall {
private boolean[][] adjMat;
WarShall(int size) {
...
当每个任务有前后置关系时，需要找到一种满足前后置关系的路线，将任务完成。
如果将每个任务看成一个节点，任务之间的前后置关系表示为有向图时，这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。
这里的图用邻接矩阵法表示，算法的关键是：
1 找到一个没有后继的顶点
2 在图中删除它，放入结果数组中
3 重复 步骤 1 ，步骤 2 直到图中没有多余的节点。
如果图中出现环装结构，则算法无法进行，因为此时任务之间循环成为前置。
关于邻接矩阵法请参见：Graph 图－邻接表法。
要注意的是：满足前后置关系的路径可能不止一条。这里仅仅得到其中的一条。
关键API：
&n ...
如果一个图中所有点都是联通的，求最小树可以将图遍历完成，这里的最小是指边最少，跟边长没有关系。
算法利用深度优先遍历，记载每个遍历过的节点，将节点按照遍历顺序记录下来就是所谓的最小树。
关于深度优先遍历请参见深度优先遍历。
不过这里奇怪的是：
假如所有节点之间是双向联通的，只用生成一个数组，装入所有的节点，例如{'a','b','c','d','d'}
然后每两个点之间的线段就是最小树的结果，即a --> b, b --> c, c --> d, d --> e
似乎不用图这样复杂的结构支撑。
不过这里还是给出了按照图来产生最小树的办法。
G ...
这里的图的广度优先遍历算法利用了队来实现。
图的深度遍历原则：
1 如果有可能，访问所有领接的未访问的节点，标记它们，并把它们放入队中。
2 当不能执行规则 1 时，如果对不为空，则从队中弹出头元素。重新执行规则 1
3 如果不能执行规则 1 和规则 2 时，则完成了遍历。
代码中的图使用的是Graph 图－邻接矩阵法
来表示，其他的表示法请见：Graph 图－邻接表法
代码中的Queue为辅助结构，用来记载访问过的节点。队列的详细描述可以见：Queue 队
，LinkedQueue 队
Vertex表示图中的节点，其中包含访问，是否访问，清除访问标志的方法。
Gr ...
这里的图的深度优先算法利用了栈来实现。
图的深度遍历原则：
1 如果有可能，访问一个领接的未访问的节点，标记它，并把它放入栈中。
2 当不能执行规则 1 时，如果栈不为空，则从栈中弹出一个元素。
3 如果不能执行规则 1 和规则 2 时，则完成了遍历。
代码中的图使用的是Graph 图－邻接矩阵法
来表示，其他的表示法请见：Graph 图－邻接表法
代码中的Stack为辅助结构，用来记载访问过的节点。栈的详细描述可以见：ArrayStack 栈
，LinkedStack 栈
。
Vertex表示图中的节点，其中包含访问，是否访问，清除访问标志的方法。
Graph.ma ...
将指定数组全排列打印，此处使用递归算法。
其核心是，轮流将数组中每个数字放在第一位上，然后调用剩下n-1个数字的全排列。以此形成递归。
以下是代码：
class Arrangement {
public static void main(String[] args) {
int[] a = {1,2,3,4};
print(a,0,true);
}
public static void print(int [] a, int offSet, boolean needPrint) {
if(n ...
评论排行榜