DepthFirstPaths.java public class DepthFirstPaths { private boolean[] marked; //
ID: 3741490 • Letter: D
Question
DepthFirstPaths.java
public class DepthFirstPaths {
private boolean[] marked; // marked[v] = is there an s-v path?
private int[] edgeTo; // edgeTo[v] = last edge on s-v path
private final int s; // source vertex
/**
* Computes a path between <tt>s</tt> and every other vertex in graph <tt>G</tt>.
* @param G the graph you built in the previous assignment, make sure it has the adjacency list adj for each vertex
* @param s the source vertex
*/
public DepthFirstPaths(Graph G, int s) {
//initialize marked, edgeTo and s
dfs(G, s);
}
// depth first search from v
private void dfs(Graph G, int v) {
//write your dfs code here. Edit edgeTo and marked whenever necessary. It would be easy to use recursion in this function
}
/**
* Is there a path between the source vertex <tt>s</tt> and vertex <tt>v</tt>?
* @param v the vertex
* @return <tt>true</tt> if there is a path, <tt>false</tt> otherwise
*/
public boolean hasPathTo(int v) {
//return something that represents the above task.
}
/**
* Returns a path between the source vertex <tt>s</tt> and vertex <tt>v</tt>, or
* <tt>null</tt> if no such path.
* @param v the vertex
* @return the sequence of vertices on a path between the source vertex
* <tt>s</tt> and vertex <tt>v</tt>, as an Iterable
*/
public Iterable<Integer> pathTo(int v) {
//implement your code
}
/**
* Unit tests the <tt>DepthFirstPaths</tt> data type.
*/
}
mediumG.txt
250
1273
244 246
239 240
238 245
235 238
233 240
232 248
231 248
229 249
228 241
226 231
223 242
223 249
222 225
220 247
219 221
218 224
218 227
217 232
216 232
214 219
214 221
213 235
213 238
212 214
212 219
212 221
212 244
211 222
211 225
210 212
210 214
210 219
210 221
210 244
209 211
209 222
209 225
208 226
208 231
207 210
207 212
207 214
207 219
207 221
207 244
206 209
205 207
205 210
205 214
205 219
205 221
204 222
204 225
204 231
203 249
202 204
202 209
202 211
202 222
202 225
201 216
201 217
201 232
201 248
200 203
200 223
200 249
199 237
198 223
198 242
197 230
196 205
196 214
196 219
195 238
195 245
194 220
193 243
192 243
191 202
191 204
191 222
191 225
191 231
190 220
190 247
189 200
189 203
189 220
189 249
188 230
188 233
188 240
187 208
187 226
187 231
187 248
186 189
186 203
186 249
185 201
185 232
185 248
184 188
184 197
184 230
183 215
182 198
182 223
182 242
181 184
181 188
181 196
181 230
180 213
179 193
179 212
179 244
178 236
177 186
177 189
177 203
177 249
176 191
176 202
176 204
176 222
176 225
175 246
174 179
174 192
174 243
172 180
172 197
172 213
172 235
171 172
171 180
171 213
171 235
171 238
171 245
170 182
170 198
170 223
170 229
170 249
169 177
169 186
169 189
169 190
169 220
168 187
168 204
168 208
168 226
168 231
168 248
167 224
166 236
165 171
165 172
165 180
165 191
165 213
164 190
164 194
164 220
164 247
163 202
163 209
163 211
163 222
163 225
162 192
161 169
161 177
161 186
161 189
161 229
161 249
160 168
160 176
160 187
160 191
160 202
160 204
160 225
160 231
159 234
159 239
158 170
158 200
158 203
158 223
158 229
158 249
157 181
157 184
157 188
157 197
157 230
156 196
156 205
156 207
156 210
156 212
156 214
156 219
156 221
155 165
155 171
155 172
155 180
155 197
155 213
155 235
155 238
154 171
154 195
154 235
154 238
154 245
153 228
153 241
152 179
152 207
152 210
152 212
152 221
152 244
152 246
151 168
151 187
151 208
151 226
151 231
150 164
150 169
150 177
150 186
150 189
150 190
150 203
150 220
149 163
149 206
149 209
149 211
149 222
149 225
148 157
148 181
148 184
148 188
148 197
148 230
147 162
147 166
146 218
146 224
146 227
145 146
144 168
144 185
144 187
144 201
144 204
144 231
144 232
144 248
143 152
143 175
143 179
143 193
143 212
143 244
143 246
142 154
142 155
142 165
142 171
142 172
142 180
142 195
142 213
142 235
142 238
140 147
140 162
139 156
139 196
139 205
139 210
139 214
139 219
139 221
138 151
138 188
138 226
138 233
138 239
138 240
137 145
137 146
137 183
137 215
137 218
137 224
137 227
136 159
136 234
135 141
135 181
135 230
134 137
134 145
134 146
134 227
133 166
132 154
132 171
132 235
132 238
131 143
131 179
131 193
131 243
130 194
130 234
129 133
129 147
129 166
129 178
129 236
128 136
128 159
128 173
128 239
126 183
126 215
125 148
125 157
125 172
125 181
125 184
125 197
125 230
124 142
124 155
124 165
124 171
124 172
124 180
124 197
124 213
124 235
123 175
123 246
122 139
122 156
122 196
122 205
122 207
122 210
122 214
122 219
122 221
121 158
121 170
121 182
121 198
121 223
121 242
120 145
120 161
120 229
119 120
119 134
119 137
119 145
119 146
119 227
118 124
118 142
118 151
118 155
118 165
118 172
118 180
118 184
118 197
118 208
118 213
117 140
117 147
117 167
117 178
117 236
116 164
116 190
116 194
116 220
116 247
115 153
115 228
115 241
114 163
114 176
114 191
114 202
114 204
114 209
114 211
114 222
114 225
113 121
113 158
113 170
113 182
113 198
113 223
113 242
112 128
112 136
112 159
112 234
112 239
110 122
110 139
110 156
110 196
110 205
110 207
110 210
110 212
110 214
110 219
110 221
109 126
109 137
109 146
109 183
109 215
109 218
108 110
108 122
108 135
108 139
108 156
108 181
108 196
108 205
108 214
108 219
107 130
107 173
107 200
107 203
106 123
106 131
106 143
106 179
106 193
106 243
106 246
105 106
105 123
105 131
105 143
105 193
105 243
105 246
104 144
104 185
104 201
104 217
104 232
104 248
103 174
103 192
103 243
102 138
102 187
102 226
102 240
101 108
101 110
101 122
101 125
101 139
101 156
101 157
101 181
101 196
101 205
101 214
101 219
100 103
100 133
100 174
100 192
99 129
99 140
99 147
99 162
98 117
98 178
98 236
97 144
97 160
97 168
97 176
97 185
97 191
97 202
97 204
97 225
97 231
97 248
96 199
96 237
95 115
95 153
95 216
94 141
94 198
94 242
93 97
93 144
93 160
93 168
93 176
93 185
93 187
93 191
93 202
93 204
93 226
93 231
93 248
92 122
92 132
92 139
92 171
92 172
92 205
92 235
91 109
91 119
91 134
91 137
91 145
91 146
91 218
91 224
91 227
90 113
90 173
90 233
90 242
89 116
89 127
89 130
89 164
89 194
88 98
88 182
87 111
87 130
87 136
87 194
87 234
86 108
86 135
86 141
85 152
85 175
85 246
84 100
84 103
84 106
84 131
84 174
84 179
84 192
84 193
84 243
83 95
83 104
83 201
83 217
83 232
82 85
82 152
82 175
82 207
82 212
82 244
82 246
81 119
81 134
81 146
81 227
81 229
80 97
80 149
80 202
80 204
80 225
79 84
79 110
79 174
79 179
79 212
79 214
78 112
78 128
78 138
78 159
78 239
78 240
77 78
77 102
77 138
77 151
77 187
77 208
77 226
77 240
76 95
76 115
76 153
76 228
76 241
75 89
75 116
75 164
75 190
75 194
75 220
75 247
74 109
74 126
74 183
74 215
73 120
73 145
72 107
72 150
72 177
72 186
72 189
72 200
72 203
72 220
72 249
71 135
71 148
71 157
71 181
71 184
71 188
71 230
71 233
71 240
70 79
70 84
70 100
70 174
70 179
70 212
70 214
70 244
69 107
69 128
69 173
68 114
68 160
68 165
68 176
68 191
68 202
68 204
68 222
67 83
67 112
67 217
66 149
66 206
66 209
65 71
65 125
65 138
65 148
65 151
65 157
65 181
65 184
65 188
65 197
65 208
65 230
65 240
64 91
64 109
64 119
64 134
64 137
64 145
64 146
64 183
64 215
64 218
64 227
63 96
63 199
63 237
62 71
62 78
62 90
62 128
62 138
62 188
62 233
62 239
62 240
61 87
61 89
61 111
61 130
61 194
61 234
60 63
60 96
60 111
60 199
60 237
59 80
59 97
59 144
59 185
59 204
59 225
59 248
58 68
58 114
58 163
58 176
58 191
58 202
58 204
58 209
58 211
58 222
57 65
57 118
57 125
57 148
57 151
57 157
57 172
57 181
57 184
57 188
57 197
57 208
57 230
56 73
56 119
56 120
56 145
56 161
55 67
55 78
55 112
55 128
55 136
55 159
55 217
55 239
54 99
54 117
54 140
54 147
53 56
53 73
53 81
53 119
53 120
53 134
53 145
53 229
52 77
52 93
52 102
52 151
52 168
52 187
52 208
52 226
52 231
51 70
51 79
51 86
51 110
51 133
51 214
50 59
50 80
50 97
50 104
50 144
50 185
50 201
50 232
50 248
49 59
49 80
49 93
49 97
49 144
49 160
49 176
49 185
49 191
49 202
49 204
49 222
49 225
49 248
48 50
48 83
48 104
48 144
48 185
48 201
48 216
48 217
48 232
48 248
47 64
47 91
47 109
47 137
47 146
47 167
47 218
47 224
46 161
46 169
46 177
46 186
45 48
45 67
45 76
45 83
45 95
45 104
45 217
45 232
44 49
44 59
44 68
44 80
44 93
44 97
44 144
44 160
44 168
44 176
44 185
44 191
44 202
44 204
44 222
44 225
44 231
44 248
43 82
43 152
43 156
43 207
43 210
43 212
43 219
43 221
43 244
42 86
42 101
42 108
42 135
42 141
42 157
42 181
42 196
41 81
41 88
41 121
41 170
41 182
41 198
40 75
40 89
40 116
40 150
40 164
40 190
40 194
40 220
40 247
39 66
39 80
39 149
39 206
39 209
39 211
38 74
38 109
38 126
38 183
38 215
37 76
37 95
37 115
37 153
37 228
37 241
36 41
36 88
36 98
36 182
35 36
35 41
35 88
35 94
35 141
35 198
34 53
34 56
34 73
34 120
34 145
33 58
33 114
33 163
33 222
32 52
32 77
32 93
32 102
32 104
32 144
32 151
32 160
32 168
32 185
32 187
32 201
32 208
32 226
32 231
32 248
31 37
31 115
31 153
31 228
31 241
30 43
30 70
30 79
30 82
30 143
30 152
30 156
30 179
30 207
30 210
30 212
30 214
30 219
30 221
30 244
29 47
29 64
29 91
29 109
29 137
29 146
29 167
29 218
29 224
29 227
28 35
28 41
28 94
28 113
28 121
28 170
28 182
28 198
28 223
28 242
27 62
27 65
27 71
27 138
27 184
27 188
27 230
27 233
27 240
26 55
26 77
26 78
26 102
26 138
26 217
26 226
26 239
26 240
25 60
25 63
25 96
25 111
25 199
24 39
24 66
24 80
24 114
24 149
24 163
24 206
24 209
24 211
24 222
24 225
23 33
23 58
23 68
23 114
23 176
23 195
23 222
22 34
22 53
22 56
22 73
22 120
22 145
21 27
21 62
21 65
21 71
21 138
21 184
21 188
21 230
21 233
21 240
20 40
20 75
20 89
20 116
20 127
20 164
20 190
20 194
20 220
20 247
19 70
19 79
19 84
19 100
19 103
19 174
19 179
19 192
19 243
18 35
18 51
18 86
18 94
18 141
17 41
17 81
17 121
17 134
17 158
17 170
17 182
17 223
17 229
16 54
16 98
16 99
16 117
16 129
16 140
16 147
16 166
16 178
16 236
15 24
15 39
15 49
15 58
15 66
15 80
15 114
15 149
15 163
15 202
15 204
15 209
15 211
15 222
15 225
14 18
14 51
14 86
14 129
14 133
14 166
13 19
13 100
13 103
13 129
13 133
13 162
13 174
13 192
12 28
12 35
12 36
12 41
12 88
12 94
12 113
12 121
12 170
12 182
12 198
12 242
11 30
11 43
11 82
11 85
11 143
11 152
11 175
11 207
11 212
11 244
11 246
10 105
10 106
10 123
10 175
10 246
9 23
9 33
9 58
9 68
9 114
9 142
9 195
8 11
8 30
8 43
8 82
8 85
8 143
8 152
8 179
8 207
8 210
8 212
8 221
8 244
8 246
7 42
7 57
7 65
7 71
7 101
7 125
7 148
7 157
7 181
7 184
7 188
7 197
7 230
6 16
6 54
6 98
6 99
6 117
6 129
6 140
6 147
6 166
6 178
6 236
5 26
5 32
5 55
5 67
5 77
5 102
5 104
5 217
5 226
4 5
4 26
4 55
4 77
4 78
4 112
4 128
4 138
4 159
4 239
4 240
3 37
3 45
3 67
3 76
3 115
3 153
3 228
3 241
2 14
2 18
2 42
2 51
2 79
2 86
2 108
2 110
2 141
1 72
1 107
1 130
1 150
1 164
1 189
1 194
1 200
1 203
1 220
0 15
0 24
0 44
0 49
0 58
0 59
0 68
0 80
0 97
0 114
0 149
0 160
0 163
0 176
0 191
0 202
0 204
0 209
0 211
0 222
0 225
Explanation / Answer
ANS:-
program:
//DepthFirstPaths.java
public class DepthFirstPaths {
//booleann
private boolean[] marked;
private int[] edgeTo;
// source_verex
private final int s;
// graph G int s
public DepthFirstPaths(Graph G, int s) {
this.s = s;
edgeTo = new int[G.V()];
marked = new boolean[G.V()];
validateVertex(s);
dfs(G, s);
}
// depth_first_search from "v"
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
}
//path
public boolean hasPathTo(int v) {
validateVertex(v);
//return
return marked[v];
}
//iterabl
public Iterable<Integer> pathTo(int v) {
validateVertex(v);
// doesnt has path
if (!hasPathTo(v))
// returns_nul
return null;
Stack<Integer> path = new Stack<Integer>();
// for loop
for (int x = v; x != s; x = edgeTo[x])
// push
path.push(x);
path.push(s);
// return
return path;
}
// throws an IllegalArgumentException if unless the {@code 0 <= v < V}
private void validateVertex(int v) {
int V = marked.length;
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
// driver progrm
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
int s = Integer.parseInt(args[1]);
DepthFirstPaths dfs = new DepthFirstPaths(G, s);
for (int v = 0; v < G.V(); v++) {
if (dfs.hasPathTo(v)) {
StdOut.printf("%d to %d: ", s, v);
for (int x : dfs.pathTo(v)) {
if (x == s) StdOut.print(x);
else
StdOut.print("-" + x);
}
StdOut.println();
}
else {
StdOut.printf("%d to %d: not connected ", s, v);
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.