Skip to content

Commit 722da5d

Browse files
byhiegbyhieg
committed
增加无向图的链接矩阵存储以及DFS，BFS，dijkstra算法
1 parent 2d5db31 commit 722da5d

4 files changed

Lines changed: 233 additions & 13 deletions

File tree

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

Lines changed: 17 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -156,6 +156,8 @@ public void preOrder2(Node node) {
156156
stack.push(tmp.left);
157157
}
158158
}
159+
System.out.println("结束");
160+
159161
}
160162
}
161163

@@ -179,6 +181,8 @@ public void inorder2(Node node) {
179181
cur = cur.left;
180182
}
181183
}
184+
System.out.println("结束");
185+
182186
}
183187
}
184188

@@ -211,6 +215,8 @@ public void postOrder2(Node node) {
211215
while (!result.isEmpty()) {
212216
System.out.print(result.pop().data + "-->");
213217
}
218+
System.out.println("结束");
219+
214220
}
215221
}
216222

@@ -232,9 +238,13 @@ public void levelRead(Node root) {
232238
queue.offer(current.right);
233239
}
234240
}
241+
System.out.println("结束");
242+
235243
}
236244

237245

246+
247+
238248
/**
239249
* 得到树中最小的节点
240250
*
@@ -270,14 +280,16 @@ public Node getMaxNode() {
270280
}
271281

272282

283+
/**
284+
* 从先序遍历和中序遍历中构造出树
285+
* @param preOrders
286+
* @param inOrders
287+
* @param r
288+
*/
273289
public void getTree(int[] preOrders, int[] inOrders,Node r) {
274290
int root = preOrders[0];
275-
// if (isLeft) {
276-
// System.out.println("左" + root);
277-
// }else{
278-
// System.out.println("右" + root);
279-
// }
280291
r.data = root;
292+
281293
int index = findIndex(inOrders, root);
282294
int[] left = new int[index];
283295
int[] preLeft = new int[index];

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

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
1+
package cn.byhieg.algorithmtutorial;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* Created by shiqifeng on 2017/4/5.
8+
* Mail byhieg@gmail.com
9+
*/
10+
public class GraphMatrix {
11+
12+
Weight[][] graph;
13+
boolean[] isVisited;
14+
15+
private static final int UNREACH = Integer.MAX_VALUE - 1000;
16+
17+
public GraphMatrix(Weight[][] graph) {
18+
this.graph = graph;
19+
}
20+
21+
/**
22+
* 图的BFS，算法流程
23+
* 1. 首先将begin节点入队
24+
* 2. 然后判断队列是否为空,不为空，则出队一个元素，输出。
25+
* 3. 将出队的元素的所有相邻的元素且没有访问的都放进队列中，重复第二步
26+
*
27+
* 广度优先遍历，从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
28+
* @param begin
29+
*/
30+
public void BFS(Integer begin) {
31+
isVisited = new boolean[graph.length];
32+
for (int i = 0 ; i < isVisited.length;i++) {
33+
isVisited[i] = false;
34+
}
35+
36+
Queue<Integer> queue = new LinkedList<>();
37+
queue.offer(begin);
38+
isVisited[begin] = true;
39+
40+
while (!queue.isEmpty()) {
41+
int current = queue.poll();
42+
System.out.print(current + "-->");
43+
for (int i = 0 ; i < graph[current].length;i++) {
44+
if (i == begin) {
45+
continue;
46+
}
47+
if (graph[current][i].weight != UNREACH && !isVisited[i]) {
48+
queue.offer(i);
49+
isVisited[i] = true;
50+
}
51+
}
52+
}
53+
System.out.println("结束");
54+
}
55+
56+
57+
/**
58+
* 图的DFS算法，算法流程
59+
* 1. 从begin节点出发，输出begin节点。
60+
* 2. 循环遍历所有与begin节点相邻并且没有被访问的节点
61+
* 3. 找到一个节点，就以他为begin,递归调用DFS
62+
* @param begin
63+
*/
64+
public void DFS(Integer begin) {
65+
isVisited = new boolean[graph.length];
66+
for (int i = 0 ; i < isVisited.length;i++) {
67+
isVisited[i] = false;
68+
}
69+
doDFS(begin);
70+
System.out.println("结束");
71+
}
72+
73+
/**
74+
* 假设给定图G的初态是所有顶点均未曾访问过。
75+
* 在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：
76+
* 首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。
77+
* 若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
78+
* 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
79+
* @param begin
80+
*/
81+
private void doDFS(Integer begin) {
82+
isVisited[begin] = true;
83+
System.out.print(begin + "-->");
84+
for (int i = 0 ; i < graph[begin].length;i++) {
85+
if (graph[begin][i].weight != UNREACH && !isVisited[i]) {
86+
doDFS(i);
87+
}
88+
}
89+
}
90+
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;
113+
114+
k = i;
115+
}
116+
117+
}
118+
//将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
119+
shortPath[k] = dmin;
120+
121+
visited[k] = 1;
122+
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) {
126+
graph[start][i].weight = graph[start][k].weight + graph[k][i].weight;
127+
path[i] = path[k] + "-->" + i;
128+
}
129+
}
130+
}
131+
132+
for (int i = 0; i < n; i++) {
133+
System.out.println("从" + start + "出发到" + i + "的最短路径为：" + path[i] + " 距离为" + shortPath[i]);
134+
}
135+
}
136+
137+
138+
139+
140+
141+
142+
public static class Weight{
143+
int weight;
144+
public Weight(){
145+
this(UNREACH);
146+
}
147+
148+
public Weight(int weight) {
149+
this.weight = weight;
150+
}
151+
}
152+
}

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

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -12,23 +12,23 @@ public class FindTest extends TestCase {
1212
int result;
1313
public void setUp() throws Exception {
1414
super.setUp();
15-
nums = new int[]{1};
15+
nums = new int[]{};
1616
}
1717

1818
public void tearDown() throws Exception {
1919
System.out.println(result);
2020
}
2121

22-
// public void testBinarySerachFind() throws Exception {
23-
// result = new Find().binarySerachFind(nums,6);
24-
// }
25-
////
22+
public void testBinarySerachFind() throws Exception {
23+
result = new Find().binarySearchFind(nums,2);
24+
}
25+
2626
// public void testBinarySearchMinFind() throws Exception {
2727
// result = new Find().binarySearchMinFind(nums,1);
2828
// }
2929

30-
public void testBinarySearchMaxFind() throws Exception {
31-
result = new Find().binarySearchMaxFind(nums, 2);
32-
}
30+
// public void testBinarySearchMaxFind() throws Exception {
31+
// result = new Find().binarySearchMaxFind(nums, 2);
32+
// }
3333

3434
}

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

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package cn.byhieg.algorithmtutorialtest;
2+
3+
import cn.byhieg.algorithmtutorial.GraphMatrix;
4+
import junit.framework.TestCase;
5+
6+
/**
7+
* Created by shiqifeng on 2017/4/5.
8+
* Mail byhieg@gmail.com
9+
*/
10+
public class GraphMatrixTest extends TestCase {
11+
12+
GraphMatrix graphMatrix;
13+
GraphMatrix.Weight[][] weights;
14+
public void setUp() throws Exception {
15+
super.setUp();
16+
weights = new GraphMatrix.Weight[5][5];
17+
for (int i = 0 ; i < weights.length;i++)
18+
for (int j = 0 ; j < weights[i].length;j++){
19+
weights[i][j] = new GraphMatrix.Weight();
20+
weights[j][i] = new GraphMatrix.Weight();
21+
}
22+
23+
weights[0][1] = new GraphMatrix.Weight(100);
24+
weights[1][2] = new GraphMatrix.Weight(10);
25+
weights[2][3] = new GraphMatrix.Weight(20);
26+
weights[3][1] = new GraphMatrix.Weight(25);
27+
weights[2][4] = new GraphMatrix.Weight(20);
28+
29+
weights[1][0] = new GraphMatrix.Weight(100);
30+
weights[2][1] = new GraphMatrix.Weight(10);
31+
weights[3][2] = new GraphMatrix.Weight(20);
32+
weights[1][3] = new GraphMatrix.Weight(25);
33+
weights[4][2] = new GraphMatrix.Weight(20);
34+
35+
36+
graphMatrix = new GraphMatrix(weights);
37+
}
38+
39+
public void tearDown() throws Exception {
40+
41+
}
42+
43+
public void testBFS() throws Exception {
44+
graphMatrix.BFS(4);
45+
46+
}
47+
48+
public void testDFS() throws Exception {
49+
graphMatrix.DFS(0);
50+
}
51+
52+
public void testDijkstra() throws Exception {
53+
graphMatrix.dijkstra(0);
54+
}
55+
56+
}

0 commit comments

Comments
 (0)