使用深度优先搜索生成迷宫图时出现 ArrayIndexOutOfBoundsException
ArrayIndexOutOfBoundsException on generating maze graph with depth first search
我创建了一个程序来解决读取文本文件输入的迷宫问题。我设法使用深度优先搜索解决了它，结果在像这样的小迷宫上很好：
11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
0 5
解决中小型迷宫的一切都很好，但是当迷宫变大时，它会给我一个 ArrayIndexOutOfBoundsException 错误（见下文）。
Enter maze file: test2.txt
Enter start node: 0
Enter goal node: 1
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 207
at MazeGraph.addArc(MazeGraph.java:95)
at MazeGraph.<init>(MazeGraph.java:51)
at MazeSystem.<init>(MazeSystem.java:25)
at MazeSystem.main(MazeSystem.java:37)
Java Result: 1
我的程序应该自动读取 test2.txt（这是一个大迷宫文件）文件中有多少节点，但发生了这个错误。代码如下所示：
MazeGraph.java
import java.io.*;
import static java.lang.System.out;
import java.util.*;
/**
* This class creates a representation of Maze as a Graph by reading from a text
* file.
*
* @author Muhammad
*/
public class MazeGraph {
final int node; //For declaring constant value of a node.
int arc;
List<Integer>[] adjacencyList;
static Set<Integer> setOfNodes = new HashSet<>();
private static Scanner scanNodeSize;
/**
* This constructors takes an integer parameter for reading node indexes in
* a list of adjacent nodes.
*
* @param node - integer parameter for passing the nodes value from the file
* and create a list of adjacent nodes.
*/
MazeGraph(int node) {
this.node = node;
this.arc = 0;//initialise to empty arcs
adjacencyList = (List<Integer>[]) new List[node];
for (int index = 0; index < node; index++) {
adjacencyList[index] = new LinkedList<Integer>();
}
}
/**
* The main constructor that takes a String parameter for reading maze file.
*
* @param mazeFile
*/
public MazeGraph(String mazeFile) {
this(getNodeSize(mazeFile));
Scanner scan;
try {
//Scan maze file.
scan = new Scanner(new File(mazeFile));
/*loop when it has next integer then read two nodes from the file and add arc for it.*/
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
addArc(node1, node2);
}
} catch (FileNotFoundException ex) {
out.println(ex.getMessage());
}
}
/**
* This method returns a size of the set of nodes by taking a String
* parameter which the name of the maze file.
*
* @param mazeFile - String parameter for reading maze file for scanning the
* size of the nodes.
* @return - returns an integer value for the size of the set of nodes.
*/
public static int getNodeSize(String mazeFile) {
try {
scanNodeSize = new Scanner(new File(mazeFile));
while (scanNodeSize.hasNextInt()) {
int node1 = scanNodeSize.nextInt();
int node2 = scanNodeSize.nextInt();
setOfNodes.add(node1);
setOfNodes.add(node2);
}
return setOfNodes.size();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return setOfNodes.size();
}
/**
* This method adds an arc by adding two different nodes in array of list
* called adjacency list.
*
* @param node1 - first node.
* @param node2 - next node.
*/
private void addArc(int node1, int node2) {
arc++; //Increase arc by one whenever this addArc method is called.
adjacencyList[node1].add(node2);
adjacencyList[node2].add(node1);
}
//Print the nodes and its arcs by looping through the adjacency list.
public void print() {
out.println(node + " Nodes, " + arc + " Arcs \n");
for (int fromNode = 0; fromNode < node; fromNode++) {
out.print(fromNode + " connected to ");
for (int arcNode : adjacencyList[fromNode]) {
out.print(arcNode + " ");
}
out.println();
}
}
/**
* This method returns a list of nodes to allow objects to be the target for
* "for-each" statement in order to iterate through the nodes.
*
* @param nodes - an Integer parameter for getting the number of nodes in a
* list.
* @return - returns a list of nodes.
*/
public Iterable<Integer> getAdjacencyList(int nodes) {
return adjacencyList[nodes];
}
}
在 MazeGraph.java 中，getNodeSize 方法 returns 一个用于构造函数参数的整数。为了让它工作，我必须在构造函数的参数中取出 getNodeSize 方法，而是在其中放置一些更大的值，例如 300。在堆栈跟踪中，它表示问题出在 addArc 方法中。如果它已经在其他迷宫中工作，我想弄清楚如何解决这个问题，以便它也可以自动读取大型迷宫。拜托，如果有人能解决这个问题，我将不胜感激。
这是大文件。
0 2
0 3
0 200
201 202
202 203
203 204
204 205
205 206
206 207
207 208
208 209
209 210
210 211
211 212
212 213
213 214
214 215
215 216
216 217
217 218
218 219
219 1
185 122
7 134
15 161
65 165
34 13
22 73
173 189
21 149
204 71
159 148
66 97
122 125
35 63
78 54
147 84
184 183
80 203
125 2
80 111
125 72
166 121
145 151
51 140
74 152
116 46
138 202
114 9
127 133
177 128
202 138
94 122
30 30
32 117
125 16
157 16
187 150
129 37
55 3
53 118
202 185
187 185
155 174
79 107
159 33
143 18
6 90
74 59
161 67
82 57
77 127
123 204
38 96
114 150
92 137
35 136
118 79
154 140
109 203
178 72
13 204
58 6
8 28
98 42
137 123
59 95
162 69
22 142
68 91
155 90
117 90
143 103
43 73
153 28
152 106
160 187
42 171
15 154
84 151
163 97
7 126
12 28
31 95
71 63
37 110
189 128
98 115
143 185
124 187
73 194
58 19
192 100
133 93
105 39
124 191
126 143
136 34
44 182
199 168
110 202
20 169
180 64
87 166
204 159
110 125
122 4
105 112
90 11
124 138
196 89
179 114
184 70
38 30
62 68
26 34
203 55
204 60
49 173
107 90
37 180
156 92
196 170
193 107
70 110
68 133
61 132
176 125
180 203
160 165
160 95
204 21
81 78
25 133
74 49
199 111
12 62
203 165
53 81
33 190
122 38
86 170
45 127
75 117
113 88
138 189
177 176
43 141
179 80
24 166
121 126
12 122
94 74
106 16
176 126
93 72
153 184
202 111
19 13
30 106
73 116
149 202
191 32
16 37
66 23
5 50
115 104
149 189
72 52
31 69
111 164
135 147
109 142
94 167
196 12
75 121
64 201
11 96
183 171
117 96
87 10
188 36
89 141
156 84
52 24
167 58
67 102
35 129
73 84
191 45
12 102
100 33
66 30
96 140
82 195
61 202
144 175
41 35
140 123
144 150
194 102
14 29
161 84
198 155
188 190
161 48
197 75
132 160
65 89
115 84
104 46
85 155
35 181
73 11
76 68
116 137
170 177
16 101
151 189
191 201
33 37
81 5
153 135
85 121
147 12
49 186
98 171
43 27
123 131
9 19
19 205
79 192
197 159
94 22
203 153
7 83
20 195
179 21
125 183
156 65
92 104
好的，问题出在getNodeSize(String)。你returnsetOfNodes.size()。问题是如果一个节点是单节点（即它没有连接弧），那么它就不会在迷宫文件中列出。例如，假设您的迷宫文件是“9999 1”，没有别的。然后您的 getNodeSize() 方法将 return 2。然后您的代码将节点数组实例化为大小为 2。然后您尝试在 9999 和 1 之间添加一条弧线，但收到 ArrayIndexOutOfBoundsException 因为有数组中只有两个位置，但您正在尝试索引位置 9999。
相反，您应该 return 观察到的最大节点 ID 加一。以下代码完成此操作：
/**
* This method returns a size of the set of nodes by taking a String
* parameter which the name of the maze file.
*
* @param mazeFile - String parameter for reading maze file for scanning the
* size of the nodes.
* @return - returns an integer value for the size of the set of nodes.
* @throws FileNotFoundException if the mazeFile could not be found
*/
public static int getNodeSize(String mazeFile) throws FileNotFoundException{
scanNodeSize = new Scanner(new File(mazeFile));
while (scanNodeSize.hasNextInt()) {
int node1 = scanNodeSize.nextInt();
int node2 = scanNodeSize.nextInt();
setOfNodes.add(node1);
setOfNodes.add(node2);
}
//Changes begin here
Integer max = setOfNodes.stream().reduce(Integer::max).get();
return max+1;
//Changes end here
}
注意：我删除了 try-catch 块并将其替换为 throws 声明。
更好的方法： 通常不赞成混合使用数组和 Collection。使用 HashMap:
可能更好
HashMap<Integer,List<Integer>> adjacencyList = new HashMap<>();
您可以通过调用 adjacencyList.get(nodeId) 访问任何节点的邻接表，并且您的构造函数可以更改为：
public MazeGraph(String mazeFile) {
adjacencyMap = new HashMap<>();
Scanner scan;
try {
//Scan maze file.
scan = new Scanner(new File(mazeFile));
/*loop when it has next integer then read two nodes from the file and add arc for it.*/
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
List<Integer> node1AdjList = adjacencyMap.getOrDefault(node1,new LinkedList<Integer>());
List<Integer> node2AdjList = adjacencyMap.getOrDefault(node2,new LinkedList<Integer>());
node1AdjList.add(node2);
node2AdjList.add(node1);
adjacencyMap.put(node1, node1AdjList);
adjacencyMap.put(node2, node2AdjList);
}
} catch (FileNotFoundException ex) {
out.println(ex.getMessage());
}
node = adjacencyMap.keySet().parallelStream().reduce(Integer::max).get();
}
我创建了一个程序来解决读取文本文件输入的迷宫问题。我设法使用深度优先搜索解决了它，结果在像这样的小迷宫上很好：
11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
0 5
解决中小型迷宫的一切都很好，但是当迷宫变大时，它会给我一个 ArrayIndexOutOfBoundsException 错误（见下文）。
Enter maze file: test2.txt
Enter start node: 0
Enter goal node: 1
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 207
at MazeGraph.addArc(MazeGraph.java:95)
at MazeGraph.<init>(MazeGraph.java:51)
at MazeSystem.<init>(MazeSystem.java:25)
at MazeSystem.main(MazeSystem.java:37)
Java Result: 1
我的程序应该自动读取 test2.txt（这是一个大迷宫文件）文件中有多少节点，但发生了这个错误。代码如下所示：
MazeGraph.java
import java.io.*;
import static java.lang.System.out;
import java.util.*;
/**
* This class creates a representation of Maze as a Graph by reading from a text
* file.
*
* @author Muhammad
*/
public class MazeGraph {
final int node; //For declaring constant value of a node.
int arc;
List<Integer>[] adjacencyList;
static Set<Integer> setOfNodes = new HashSet<>();
private static Scanner scanNodeSize;
/**
* This constructors takes an integer parameter for reading node indexes in
* a list of adjacent nodes.
*
* @param node - integer parameter for passing the nodes value from the file
* and create a list of adjacent nodes.
*/
MazeGraph(int node) {
this.node = node;
this.arc = 0;//initialise to empty arcs
adjacencyList = (List<Integer>[]) new List[node];
for (int index = 0; index < node; index++) {
adjacencyList[index] = new LinkedList<Integer>();
}
}
/**
* The main constructor that takes a String parameter for reading maze file.
*
* @param mazeFile
*/
public MazeGraph(String mazeFile) {
this(getNodeSize(mazeFile));
Scanner scan;
try {
//Scan maze file.
scan = new Scanner(new File(mazeFile));
/*loop when it has next integer then read two nodes from the file and add arc for it.*/
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
addArc(node1, node2);
}
} catch (FileNotFoundException ex) {
out.println(ex.getMessage());
}
}
/**
* This method returns a size of the set of nodes by taking a String
* parameter which the name of the maze file.
*
* @param mazeFile - String parameter for reading maze file for scanning the
* size of the nodes.
* @return - returns an integer value for the size of the set of nodes.
*/
public static int getNodeSize(String mazeFile) {
try {
scanNodeSize = new Scanner(new File(mazeFile));
while (scanNodeSize.hasNextInt()) {
int node1 = scanNodeSize.nextInt();
int node2 = scanNodeSize.nextInt();
setOfNodes.add(node1);
setOfNodes.add(node2);
}
return setOfNodes.size();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return setOfNodes.size();
}
/**
* This method adds an arc by adding two different nodes in array of list
* called adjacency list.
*
* @param node1 - first node.
* @param node2 - next node.
*/
private void addArc(int node1, int node2) {
arc++; //Increase arc by one whenever this addArc method is called.
adjacencyList[node1].add(node2);
adjacencyList[node2].add(node1);
}
//Print the nodes and its arcs by looping through the adjacency list.
public void print() {
out.println(node + " Nodes, " + arc + " Arcs \n");
for (int fromNode = 0; fromNode < node; fromNode++) {
out.print(fromNode + " connected to ");
for (int arcNode : adjacencyList[fromNode]) {
out.print(arcNode + " ");
}
out.println();
}
}
/**
* This method returns a list of nodes to allow objects to be the target for
* "for-each" statement in order to iterate through the nodes.
*
* @param nodes - an Integer parameter for getting the number of nodes in a
* list.
* @return - returns a list of nodes.
*/
public Iterable<Integer> getAdjacencyList(int nodes) {
return adjacencyList[nodes];
}
}
在 MazeGraph.java 中，getNodeSize 方法 returns 一个用于构造函数参数的整数。为了让它工作，我必须在构造函数的参数中取出 getNodeSize 方法，而是在其中放置一些更大的值，例如 300。在堆栈跟踪中，它表示问题出在 addArc 方法中。如果它已经在其他迷宫中工作，我想弄清楚如何解决这个问题，以便它也可以自动读取大型迷宫。拜托，如果有人能解决这个问题，我将不胜感激。
这是大文件。
0 2
0 3
0 200
201 202
202 203
203 204
204 205
205 206
206 207
207 208
208 209
209 210
210 211
211 212
212 213
213 214
214 215
215 216
216 217
217 218
218 219
219 1
185 122
7 134
15 161
65 165
34 13
22 73
173 189
21 149
204 71
159 148
66 97
122 125
35 63
78 54
147 84
184 183
80 203
125 2
80 111
125 72
166 121
145 151
51 140
74 152
116 46
138 202
114 9
127 133
177 128
202 138
94 122
30 30
32 117
125 16
157 16
187 150
129 37
55 3
53 118
202 185
187 185
155 174
79 107
159 33
143 18
6 90
74 59
161 67
82 57
77 127
123 204
38 96
114 150
92 137
35 136
118 79
154 140
109 203
178 72
13 204
58 6
8 28
98 42
137 123
59 95
162 69
22 142
68 91
155 90
117 90
143 103
43 73
153 28
152 106
160 187
42 171
15 154
84 151
163 97
7 126
12 28
31 95
71 63
37 110
189 128
98 115
143 185
124 187
73 194
58 19
192 100
133 93
105 39
124 191
126 143
136 34
44 182
199 168
110 202
20 169
180 64
87 166
204 159
110 125
122 4
105 112
90 11
124 138
196 89
179 114
184 70
38 30
62 68
26 34
203 55
204 60
49 173
107 90
37 180
156 92
196 170
193 107
70 110
68 133
61 132
176 125
180 203
160 165
160 95
204 21
81 78
25 133
74 49
199 111
12 62
203 165
53 81
33 190
122 38
86 170
45 127
75 117
113 88
138 189
177 176
43 141
179 80
24 166
121 126
12 122
94 74
106 16
176 126
93 72
153 184
202 111
19 13
30 106
73 116
149 202
191 32
16 37
66 23
5 50
115 104
149 189
72 52
31 69
111 164
135 147
109 142
94 167
196 12
75 121
64 201
11 96
183 171
117 96
87 10
188 36
89 141
156 84
52 24
167 58
67 102
35 129
73 84
191 45
12 102
100 33
66 30
96 140
82 195
61 202
144 175
41 35
140 123
144 150
194 102
14 29
161 84
198 155
188 190
161 48
197 75
132 160
65 89
115 84
104 46
85 155
35 181
73 11
76 68
116 137
170 177
16 101
151 189
191 201
33 37
81 5
153 135
85 121
147 12
49 186
98 171
43 27
123 131
9 19
19 205
79 192
197 159
94 22
203 153
7 83
20 195
179 21
125 183
156 65
92 104
好的，问题出在getNodeSize(String)。你returnsetOfNodes.size()。问题是如果一个节点是单节点（即它没有连接弧），那么它就不会在迷宫文件中列出。例如，假设您的迷宫文件是“9999 1”，没有别的。然后您的 getNodeSize() 方法将 return 2。然后您的代码将节点数组实例化为大小为 2。然后您尝试在 9999 和 1 之间添加一条弧线，但收到 ArrayIndexOutOfBoundsException 因为有数组中只有两个位置，但您正在尝试索引位置 9999。
相反，您应该 return 观察到的最大节点 ID 加一。以下代码完成此操作：
/**
* This method returns a size of the set of nodes by taking a String
* parameter which the name of the maze file.
*
* @param mazeFile - String parameter for reading maze file for scanning the
* size of the nodes.
* @return - returns an integer value for the size of the set of nodes.
* @throws FileNotFoundException if the mazeFile could not be found
*/
public static int getNodeSize(String mazeFile) throws FileNotFoundException{
scanNodeSize = new Scanner(new File(mazeFile));
while (scanNodeSize.hasNextInt()) {
int node1 = scanNodeSize.nextInt();
int node2 = scanNodeSize.nextInt();
setOfNodes.add(node1);
setOfNodes.add(node2);
}
//Changes begin here
Integer max = setOfNodes.stream().reduce(Integer::max).get();
return max+1;
//Changes end here
}
注意：我删除了 try-catch 块并将其替换为 throws 声明。
更好的方法： 通常不赞成混合使用数组和 Collection。使用 HashMap:
HashMap<Integer,List<Integer>> adjacencyList = new HashMap<>();
您可以通过调用 adjacencyList.get(nodeId) 访问任何节点的邻接表，并且您的构造函数可以更改为：
public MazeGraph(String mazeFile) {
adjacencyMap = new HashMap<>();
Scanner scan;
try {
//Scan maze file.
scan = new Scanner(new File(mazeFile));
/*loop when it has next integer then read two nodes from the file and add arc for it.*/
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
List<Integer> node1AdjList = adjacencyMap.getOrDefault(node1,new LinkedList<Integer>());
List<Integer> node2AdjList = adjacencyMap.getOrDefault(node2,new LinkedList<Integer>());
node1AdjList.add(node2);
node2AdjList.add(node1);
adjacencyMap.put(node1, node1AdjList);
adjacencyMap.put(node2, node2AdjList);
}
} catch (FileNotFoundException ex) {
out.println(ex.getMessage());
}
node = adjacencyMap.keySet().parallelStream().reduce(Integer::max).get();
}