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 s and every other vertex in graph G.

* @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 s and vertex v?

* @param v the vertex

* @return true if there is a path, false otherwise

*/

public boolean hasPathTo(int v) {

//return something that represents the above task.

}

/**

* Returns a path between the source vertex s and vertex v, or

* null if no such path.

* @param v the vertex

* @return the sequence of vertices on a path between the source vertex

* s and vertex v, as an Iterable

*/

public Iterable pathTo(int v) {

//implement your code

}

/**

* Unit tests the DepthFirstPaths 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

Write a class DepthFirstPaths.java to implement a Depth First Search algorithm using the pseudocode given below. Alternatively you can download the file DepthFirstPaths.java and implement all the unimplemented methods of the class so that it performs Depth First Search on graph G. See the pseudocode given below DFS(G) 1 for each vertex u E G. V 2 u.colorWHITE u.? = NIL 4 time0 5 for each vertex u E G. V if u. color == WHITE DFS-VISIT (G, u) DFS-VISIT (G, u) // white vertex u has just been discovered tmetime +1 2 u.dtime 3 u.color= GRAY 4 for each v e G.Adjlu] /l explore edge (u, v) if v.colorWHITE DFS-VISIT (G, v) // blacken u; it is finished u,color BLACK 9 tme time +1 10 u.f= time