Our solution to reporting a path fromu to v in Code Fragment 14.6 could bemade more efficient in practice if the DFS process ended as soon as v is discovered. Describe how to modify our code base to implement this optimization.

Transcribed Image Text:

1 / ** Returns an ordered list of edges comprising the directed path from u to v. 2 public static PositionalList> 3 constructPath(Graph g, Vertex u, Vertex v, 4 Map,Edge> forest) { Positional List> path if (forest.get(v) != null) { 7 new LinkedPositional List<>(); // v was discovered during the search // we construct the path from back to front 5 %3D 6. Vertex walk = v; while (walk != u) { Edge edge = forest.get(walk); path.addFirst(edge); walk = g.opposite(walk, edge); } } return path; 8 9 10 // add edge to *front* of path // repeat with opposite endpoint 11 12 13 14 15 }