Skip to content

Commit 1fa4408

Browse files
byhiegbyhieg
committed
Merge branch 'master' of https://github.com/byhieg/JavaTutorial 
2 parents 93dccc0 + cda002d commit 1fa4408

4 files changed

Lines changed: 69 additions & 50 deletions

File tree

‎images/JavaTutorial目录.jpg‎

172 KB
Loading

‎src/main/java/cn/byhieg/algorithmtutorial/GraphMatrix.java‎

Lines changed: 62 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
package cn.byhieg.algorithmtutorial;
22

3-
import java.util.LinkedList;
4-
import java.util.Queue;
3+
import java.util.*;
54

65
/**
76
* Created by shiqifeng on 2017/4/5.
@@ -12,7 +11,7 @@ public class GraphMatrix {
1211
Weight[][] graph;
1312
boolean[] isVisited;
1413

15-
private static final int UNREACH = Integer.MAX_VALUE - 1000;
14+
private static final int UNREACH = Integer.MAX_VALUE >> 1;
1615

1716
public GraphMatrix(Weight[][] graph) {
1817
this.graph = graph;
@@ -23,13 +22,14 @@ public GraphMatrix(Weight[][] graph) {
2322
* 1. 首先将begin节点入队
2423
* 2. 然后判断队列是否为空,不为空，则出队一个元素，输出。
2524
* 3. 将出队的元素的所有相邻的元素且没有访问的都放进队列中，重复第二步
26-
*
25+
* <p>
2726
* 广度优先遍历，从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
27+
*
2828
* @param begin
2929
*/
3030
public void BFS(Integer begin) {
3131
isVisited = new boolean[graph.length];
32-
for (int i = 0 ; i < isVisited.length;i++) {
32+
for (int i = 0; i < isVisited.length; i++) {
3333
isVisited[i] = false;
3434
}
3535

@@ -40,7 +40,7 @@ public void BFS(Integer begin) {
4040
while (!queue.isEmpty()) {
4141
int current = queue.poll();
4242
System.out.print(current + "-->");
43-
for (int i = 0 ; i < graph[current].length;i++) {
43+
for (int i = 0; i < graph[current].length; i++) {
4444
if (i == begin) {
4545
continue;
4646
}
@@ -59,11 +59,12 @@ public void BFS(Integer begin) {
5959
* 1. 从begin节点出发，输出begin节点。
6060
* 2. 循环遍历所有与begin节点相邻并且没有被访问的节点
6161
* 3. 找到一个节点，就以他为begin,递归调用DFS
62+
*
6263
* @param begin
6364
*/
6465
public void DFS(Integer begin) {
6566
isVisited = new boolean[graph.length];
66-
for (int i = 0 ; i < isVisited.length;i++) {
67+
for (int i = 0; i < isVisited.length; i++) {
6768
isVisited[i] = false;
6869
}
6970
doDFS(begin);
@@ -76,72 +77,85 @@ public void DFS(Integer begin) {
7677
* 首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。
7778
* 若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
7879
* 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
80+
*
7981
* @param begin
8082
*/
8183
private void doDFS(Integer begin) {
8284
isVisited[begin] = true;
8385
System.out.print(begin + "-->");
84-
for (int i = 0 ; i < graph[begin].length;i++) {
86+
for (int i = 0; i < graph[begin].length; i++) {
8587
if (graph[begin][i].weight != UNREACH && !isVisited[i]) {
8688
doDFS(i);
8789
}
8890
}
8991
}
9092

91-
public void dijkstra(int start) {
92-
//接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中）
93-
//返回一个int[] 数组，表示从start到它的最短路径长度
94-
int n = graph.length; //顶点个数
95-
int[] shortPath = new int[n]; //存放从start到其他各点的最短路径
96-
String[] path = new String[n]; //存放从start到其他各点的最短路径的字符串表示
97-
for (int i = 0; i < n; i++)
98-
path[i] = new String(start + "-->" + i);
99-
int[] visited = new int[n]; //标记当前该顶点的最短路径是否已经求出,1表示已求出
100-
101-
//初始化，第一个顶点求出
102-
shortPath[start] = 0;
103-
visited[start] = 1;
104-
105-
for (int count = 1; count <= n - 1; count++) //要加入n-1个顶点
106-
{
107-
108-
int k = -1; //选出一个距离初始顶点start最近的未标记顶点
109-
int dmin = Integer.MAX_VALUE;
110-
for (int i = 0; i < n; i++) {
111-
if (visited[i] == 0 && graph[start][i].weight < dmin) {
112-
dmin = graph[start][i].weight;
93+
/**
94+
* dijkstra 从指定起点到指定终点的最短路
95+
* paths变量，key为节点，value为start到key节点的最短路径
96+
* values变量，key为节点，value为start到key节点的最小值
97+
* 1. dijkstra的核心思想，是广义搜索，先遍历所有与start相邻的节点，且没有找过的点
98+
* 2. 找出最短的节点k，然后以最短的节点为中间节点，如果start-k-i的距离短于start-i,则修改start到i的值，并且修改start到i的路径
99+
* 3. 然后在此基础上，继续从start节点去没有找过的点，重复1
100+
* @param start
101+
* @param end
102+
*/
103+
public void dijkstra(int start, int end) {
113104

105+
106+
int n = graph.length;
107+
isVisited = new boolean[n];
108+
for (int i = 0; i < n; i++) {
109+
isVisited[i] = false;
110+
}
111+
isVisited[start] = true;
112+
HashMap<Integer,String> paths = new HashMap<>();
113+
HashMap<Integer, Integer> values = new HashMap<>();
114+
for(int i = 0 ; i < n;i++) {
115+
if (i == start) {
116+
paths.put(start, start + "");
117+
}else{
118+
paths.put(i, start + "" + i + "");
119+
}
120+
}
121+
values.put(start,0);
122+
while (!values.containsKey(end)) {
123+
int k = -1;
124+
int min = UNREACH;
125+
for (int i = 0; i < n; i++) {
126+
if (!isVisited[i] && graph[start][i].weight < min) {
127+
min = graph[start][i].weight;
114128
k = i;
115129
}
116-
117130
}
118-
//将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
119-
shortPath[k] = dmin;
120-
121-
visited[k] = 1;
131+
values.put(k, min);
132+
isVisited[k] = true;
122133

123-
//以k为中间点，修正从start到未访问各点的距离
124-
for (int i = 0; i < n; i++) { // System.out.println("k="+k);
125-
if (visited[i] == 0 && graph[start][k].weight + graph[k][i].weight < graph[start][i].weight) {
134+
for (int i = 0; i < n; i++) {
135+
if (!isVisited[i] && graph[start][k].weight + graph[k][i].weight < graph[start][i].weight) {
126136
graph[start][i].weight = graph[start][k].weight + graph[k][i].weight;
127-
path[i] = path[k] + "-->" + i;
137+
String path = paths.get(k);
138+
path += i + "";
139+
paths.put(i,path);
128140
}
129141
}
130142
}
131-
132-
for (int i = 0; i < n; i++) {
133-
System.out.println("从" + start + "出发到" + i + "的最短路径为：" + path[i] + " 距离为" + shortPath[i]);
143+
System.out.println("从起始点 " + start + " 到终点 " + end + " 的最短路");
144+
String path = paths.get(end);
145+
for(int i = 0; i < path.length();i++) {
146+
System.out.print(path.charAt(i));
147+
if (i != path.length() - 1){
148+
System.out.print("-->");
149+
}
134150
}
151+
System.out.println("最短路径的值为 " + values.get(end));
135152
}
136153

137154

138-
139-
140-
141-
142-
public static class Weight{
155+
public static class Weight {
143156
int weight;
144-
public Weight(){
157+
158+
public Weight() {
145159
this(UNREACH);
146160
}
147161

‎src/main/java/cn/byhieg/algorithmtutorial/Sort.java‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,9 @@
11
package cn.byhieg.algorithmtutorial;
22

3+
import java.util.ArrayList;
4+
import java.util.Comparator;
5+
import java.util.List;
6+
37
/**
48
* Created by shiqifeng on 2017/3/28.
59
* Mail [email protected]
@@ -202,6 +206,7 @@ public void heapSort(int[] nums) {
202206
// for (int i = 0; i < length; i++) {
203207
// swim(nums, i);
204208
// }
209+
//只能从前一半开始sink
205210
for (int i = length / 2 ; i >= 0;i--) {
206211
sink(nums,i,length);
207212
}
@@ -241,7 +246,7 @@ private void swim(int nums[], int i) {
241246
* @param nums nums[] 数组
242247
* @param i i节点
243248
*/
244-
public void sink(int nums[], int i,int n) {
249+
public void sink(int [] nums, int i,int n) {
245250
int son = 2 * i + 1;
246251
while (son <= n - 1) {
247252
if (son < n - 1 && nums[son] > nums[son + 1]) son++;

‎src/test/java/cn/byhieg/algorithmtutorialtest/GraphMatrixTest.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,7 @@ public void testDFS() throws Exception {
5050
}
5151

5252
public void testDijkstra() throws Exception {
53-
graphMatrix.dijkstra(0);
53+
graphMatrix.dijkstra(1,2);
5454
}
5555

5656
}

0 commit comments

Comments
 (0)