CS 1501讲解、辅导 Python/Java程序设计

Support for Assignment 4
CS 1501
Sherif KhattabGeneral Hints
• You can get the number of vertices using ag.getAirports().size(), whereby
ag is an AirlineGraph object
• Iterate over airports using for(String airport: ag.getAirports()){ … }
• You can get a unique integer for each airport in the graph using the
ag.getAirportNo() method
• You can retrieve the set of neighbors of an airport using
ag.adj(airportName)
• To iterate over the set of neighbors: for(Route r: ag.adj(airportName)){ … }
• You can retrieve the name of a neighboring airport using r.destination
• You may use HashSet to instantiate Set objectsfewestStops
• Use BFS
• check the pseudo-code in lecture notes
• Shortest path Source -> transit -> destination can be found by
• shortest path source  transit
• shortest path transit  destination
• concatenate the two shortest paths
• Be careful not to add transit twice to the concatenated pathConnected Components
• Use BFS
• You can find the pseudo-code in the lecture notesallTrips
• Use backtracking and pruning
• Define a recursive helper method: solve(current decision, current solution)
• current decision  current vertex (int or String) • current solution
• Set> of trips found so far
• current path: ArrayList
• total price so far of current path
• number of stops so far of current path
• destination, budget and max number of stops for comparison
• Inside the recursive helper method:
• if current vertex is the destination  add current path to the solution set and return
• iterate over all possibilities (unmarked neighbors)
• check if you can add the neighbor to the current path (total price won’t exceed budget and total number of stops won’t exceed maximum stops)
• if so, mark neighbor, update current path, its price, and its number of stops.
• make a recursive call on the neighbor
• undo changes to current path, price, and number of stops and unmark neighbor
• mark start airport before calling solve the first timeallRoundTrips
• Use backtracking and pruning
• Define a recursive helper method: solve(current decision, current solution)
• current decision  current vertex (int or String) • current solution
• Set> of trips found so far
• current path: ArrayList
• total price so far of current path
• number of stops so far of current path
• budget and max number of stops for comparison
• Inside the recursive helper method:
• if current vertex is the source and stops so far > 0  add current path to the solution set and return
• iterate over all possibilities (unmarked neighbors)
• check if you can add the neighbor to the current path (total price won’t exceed budget and total number of stops won’t exceed maximum stops)
• if so, mark neighbor, update current path, its price, and its number of stops.
• make a recursive call on the neighbor
• undo changes to current path, price, and number of stops and unmark neighbor
• Don’t mark start airport before calling solve the first time

CS 1501讲解 、辅导 Python/Java程序设计

CS 1501讲解、辅导 Python/Java程序设计