Maxim，你的代碼中有一大堆錯誤。看起來好像你有想法想要做什麼，然後向它投擲一些代碼，直到出現並工作了一點，但這裏沒有明確的概念，因此難怪它不起作用。
這個程序的核心是航班收集（爲什麼Flights大寫？），並且很有可能在它周圍建立一個工作路線查找器。我不確定它是否會幫助您更多地給您一些提示或爲您構建程序。
更新：我同時發現了一個航班時刻表波蘭航空公司（不要問！）與203條不同的路線，我可以用它來填充和測試飛行連接結構。我將開始黑客攻擊，然後我們會看到它是如何發生的。
更新：下面的代碼。爲了達到您的目的，您可能僅僅找到路線（即參觀機場的行程）可能還不夠。你可能想要一個到達那裏的航班清單。請注意，當然，可能有多個具有相同行程的航班組合 - 此代碼只能找到第一個航班。
您可能希望修改算法以在旅行時間上設置重量（=成本），如果您有這些重量，那麼您的乘客不會得到最少的腿數（=從一個機場到下一個機場的跳數），但也是最短的組合旅行時間。該算法的更一般形式將被稱爲Dijkstra算法，並且在Wikipedia中也有描述。
有趣的是，似乎BFS並不真正適合遞歸解決方案。就像您的原始代碼一樣，我的代碼基本上只需幾個循環即可完成。請注意，用於執行BFS的正確「主」數據結構不是堆棧，而是隊列！
public class Maxim {
/**
* Create a Maxim instance and run a search on it.
*/
public static void main(String[] args) {
try {
Maxim maxim = new Maxim();
Route r = maxim.findRoute("FCO", "DNV"); // tests a single origin/destination pair
if (r == null) {
System.out.println("No route found");
} else {
System.out.println(Arrays.deepToString(r.toArray()));
}
} catch (Exception e) {
e.printStackTrace();
}
}
/**
* A simple Flight. Contains a flight number and only a single leg.
* number: Flight number
* dep: Departure airport
* arr: Arrival airport
*/
class Flight {
final String number, dep, arr;
public Flight(String number, String departure, String arrival) {
this.number = number; this.dep = departure; this.arr = arrival;
}
public String toString() {
return "Flight [number=" + this.number + ", dep=" + this.dep + ", arr=" + this.arr + "]";
}
}
/**
* Airport: A city and a list of Flights originating from it.
*/
class Airport {
public final String city;
public List<Flight> flights = new ArrayList<Flight>();
public Airport(String city) {
this.city = city;
}
public String toString() {
return "Airport [city=" + this.city + ", flights=" + this.flights + "]";
}
}
/**
* Route: A list of flights that get a traveller from a given origin to a destination.
*/
static class Route extends ArrayList<Flight> { }
/**
* Our known list of flights. It's not really needed after initialization.
*/
private List<Flight> flights = new ArrayList<Flight>();
/**
* List of airports. These constitute the graph we search.
*/
private Map<String, Airport> airports = new HashMap<String, Airport>();
/**
* Constructor. Constructs the "airports" graph from a list of "flights" read from a file.
*/
public Maxim() throws Exception {
// Read flights from file into list "flights".
// The file contains strings like " 696KGDWAW" = flight number, departure airport, arrival airport
BufferedReader flightReader = new BufferedReader(new FileReader("/home/carl/XX.flights"));
while (true) {
String flt = flightReader.readLine();
if (flt == null) break;
flights.add(new Flight(flt.substring(0,4), flt.substring(4, 7), flt.substring(7, 10)));
}
flightReader.close();
// Create a map of each airport to a list of Flights departing from it.
// This is the graph we'll be doing BFS on.
for (Flight flight : flights) {
String from = flight.dep;
if (!airports.containsKey(from)) {
Airport port = new Airport(from);
port.flights.add(flight);
airports.put(from, port);
} else {
Airport port = airports.get(from);
port.flights.add(flight);
}
}
}
/**
Algorithm (from Wikipedia):
1. Enqueue the root node.
2. Dequeue a node and examine it.
If the element sought is found in this node, quit the search and return a result.
Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
3. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
4. Repeat from Step 2.
*/
public Route findRoute(String origin, String destination) {
Queue<Airport> queue = new LinkedList<Airport>();
Map<Airport, Flight> backtrack = new HashMap<Airport, Flight>();
Airport oriApt = this.airports.get(origin);
if (oriApt == null) return null; // origin airport not found - no solution
queue.add(oriApt);
while (!queue.isEmpty()) {
Airport apt = queue.remove();
if (apt == null) break;
if (apt.city.equals(destination)) { // Made it to destination; create the route and return it
Route toHere = new Route();
while (apt != oriApt) {
Flight flt = backtrack.get(apt);
toHere.add(flt);
apt = airports.get(flt.dep);
}
Collections.reverse(toHere);
return toHere;
}
// enqueue all new airports reachable from this airport.
// record the flight that got us there in backtrack.
for (Flight flt: apt.flights) {
Airport destApt = airports.get(flt.arr);
if (backtrack.containsKey(destApt)) continue; // we've been to this destination before - ignore
backtrack.put(destApt, flt);
queue.add(destApt);
}
}
// if we're here, we didn't find anything.
return null;
}
}
這是一個遞歸搜索？你沒有遞歸功能。 – 2009-12-31 13:11:05
遞歸*可以使用堆棧進行模擬，因爲OP正在嘗試這樣做。但是，這一切都很混亂。 – 2009-12-31 13:14:16
@Carl：是的，這裏沒有回溯或任何事情發生。它將穿過「飛行」對象，直到找到沒有目的地的對象，然後停止。拯救這個代碼是完全重寫它的問題。 – Welbog 2009-12-31 13:16:18