forked from damaohongtu/JavaInterview
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathTest2.java
More file actions
146 lines (131 loc) · 5.38 KB
/
Copy pathTest2.java
File metadata and controls
146 lines (131 loc) · 5.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
package BiShi.WeBank;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
public class Test2 {
/* 临时保存路径节点的栈 */
public static Stack<Node> stack = new Stack<Node>();
/* 存储路径的集合 */
public static ArrayList<Object[]> sers = new ArrayList<Object[]>();
/* 判断节点是否在栈中 */
public static boolean isNodeInStack(Node node) {
Iterator<Node> it = stack.iterator();
while (it.hasNext()) {
Node node1 = (Node) it.next();
if (node == node1)
return true;
}
return false;
}
/* 此时栈中的节点组成一条所求路径，转储并打印输出 */
public static void showAndSavePath() {
Object[] o = stack.toArray();
for (int i = 0; i < o.length; i++) {
Node nNode = (Node) o[i];
if (i < (o.length - 1))
System.out.print(nNode.getName() + "->");
else
System.out.print(nNode.getName());
}
sers.add(o); /* 转储 */
System.out.println("\n");
}
/*
* 寻找路径的方法 cNode: 当前的起始节点currentNode pNode: 当前起始节点的上一节点previousNode sNode:
* 最初的起始节点startNode eNode: 终点endNode
*/
public static boolean getPaths(Node cNode, Node pNode, Node sNode, Node eNode) {
Node nNode = null;
/* 如果符合条件判断说明出现环路，不能再顺着该路径继续寻路，返回false */
if (cNode != null && pNode != null && cNode == pNode)
return false;
if (cNode != null) {
int i = 0;
/* 起始节点入栈 */
stack.push(cNode);
/* 如果该起始节点就是终点，说明找到一条路径 */
if (cNode == eNode) {
/* 转储并打印输出该路径，返回true */
showAndSavePath();
return true;
}
/* 如果不是,继续寻路 */
else {
/*
* 从与当前起始节点cNode有连接关系的节点集中按顺序遍历得到一个节点 作为下一次递归寻路时的起始节点
*/
nNode = cNode.getRelationNodes().get(i);
while (nNode != null) {
/*
* 如果nNode是最初的起始节点或者nNode就是cNode的上一节点或者nNode已经在栈中 ， 说明产生环路
* ，应重新在与当前起始节点有连接关系的节点集中寻找nNode
*/
if (pNode != null && (nNode == sNode || nNode == pNode || isNodeInStack(nNode))) {
i++;
if (i >= cNode.getRelationNodes().size())
nNode = null;
else
nNode = cNode.getRelationNodes().get(i);
continue;
}
/* 以nNode为新的起始节点，当前起始节点cNode为上一节点，递归调用寻路方法 */
if (getPaths(nNode, cNode, sNode, eNode))/* 递归调用 */
{
/* 如果找到一条路径，则弹出栈顶节点 */
stack.pop();
}
/* 继续在与cNode有连接关系的节点集中测试nNode */
i++;
if (i >= cNode.getRelationNodes().size())
nNode = null;
else
nNode = cNode.getRelationNodes().get(i);
}
/*
* 当遍历完所有与cNode有连接关系的节点后， 说明在以cNode为起始节点到终点的路径已经全部找到
*/
stack.pop();
return false;
}
} else
return false;
}
public static void main(String[] args) {
/* 定义节点关系 */
String nodeRalation[][] = { { "0" }, // 0
{ "2" }, // 1
{ "1", "3" }, // 2
{ "2", "4", "9" }, // 3
{ "3", "5" }, // 4
{ "4" }, // 5
{ "9" }, // 6
{ "10", "8" }, // 7
{ "7", "11" }, // 8
{ "3", "6", "10" }, // 9
{ "9", "7", "11" }, // 10
{ "10", "8" } // 11
};
/* 定义节点数组 */
Node[] node = new Node[nodeRalation.length];
for (int i = 0; i < nodeRalation.length; i++) {
node[i] = new Node();
node[i].setName("node" + i);
}
/* 定义与节点相关联的节点集合 */
for (int i = 0; i < nodeRalation.length; i++) {
ArrayList<Node> List = new ArrayList<Node>();
for (int j = 0; j < nodeRalation[i].length; j++) {
for (int z = 0; z < nodeRalation.length; z++) {
if (node[z].getName().equals("node" + nodeRalation[i][j])) {
List.add(node[z]);
break;
}
}
}
node[i].setRelationNodes(List);
List = null; // 释放内存
}
/* 开始搜索所有路径 */
getPaths(node[1], null, null, node[8]);
}
}