深度优先 － 路径的选择
class PathInfo //数据存储结构{String from;String to;int distance;boolean skip; // used in backtrackingPathInfo(String f, String t, int d){from = f;to = t;distance = d;skip = false;}}public class Depth{final int MAX = 100;PathInfo paths[] = new PathInfo[MAX];int pathCount = 0;Stack<PathInfo> goInfo = new Stack<PathInfo>();public static void main(String args[]){String from = "", to = "";BufferedReader br = new BufferedReader(new InputStreamReader(System.in));try{System.out.print("From? ");from = br.readLine();System.out.print("To? ");to = br.readLine();} catch (IOException exc){System.out.println("Error on input.");}Depth depth = new Depth();depth.setup();depth.isOK(from, to);depth.route();}void isOK(String from, String to)// 将可行的路径压栈{int dist = match(from, to);if (dist != 0) // 一站到达{goInfo.push(new PathInfo(from, to, dist));return;}PathInfo pinfo = findFrom(from);if (pinfo != null){goInfo.push(new PathInfo(from, to, pinfo.distance));isOK(pinfo.to, to); // 直到有“一站到达”} else if (goInfo.size() > 0){pinfo = (PathInfo) goInfo.pop();// 死路一条isOK(pinfo.from, pinfo.to);// 回头再走，成立即可}}void route(){if (goInfo.size() == 0)return;int num = goInfo.size();Stack<PathInfo> backInfo = new Stack();for (int i = 0; i < num; i++)backInfo.push(goInfo.pop());// 倒出来,再pop，就是正序了int dist = 0;PathInfo pinfo = null;for (int i = 0; i < num; i++){pinfo = (PathInfo) backInfo.pop();System.out.print(pinfo.from + " to ");dist += pinfo.distance;}System.out.println(pinfo.to);System.out.println("Distance is " + dist);}// 看能不能直到，能的话，就返回权重，不能返回0int match(String from, String to){for (int i = pathCount - 1; i > -1; i--){if (paths[i].from.equals(from) && paths[i].to.equals(to) && !paths[i].skip){paths[i].skip = true; // prevent reusereturn paths[i].distance;}}return 0;}// Put flights into the database.void addFlight(String from, String to, int dist){if (pathCount < MAX){paths[pathCount] = new PathInfo(from, to, dist);pathCount++;} elseSystem.out.println("Flight database full.\n");}// Given from, find any connection.// 找到一个起点为from的，并再new一份出来，这段路的条件是未走过。PathInfo findFrom(String from){for (int i = 0; i < pathCount; i++){if (paths[i].from.equals(from) && !paths[i].skip){PathInfo pinfo = new PathInfo(paths[i].from, paths[i].to, paths[i].distance);paths[i].skip = true; // prevent reusereturn pinfo;}}return null;}// Initialize the path database.// 地图是有限的，每个点周边相邻的点，两两成一直线，且是有方向性的// 查找的时候，数据的分布，会影响结果public void setup(){databaseGen();}private void databaseGen(){addFlight("A", "B", 500);addFlight("A", "D", 900);addFlight("A", "C", 1800);addFlight("A", "J", 700);addFlight("J", "K", 300);addFlight("B", "A", 1700);addFlight("B", "F", 1700);// addFlight("B", "H", 600);addFlight("B", "D", 500);addFlight("C", "G", 1000);addFlight("C", "E", 1000);addFlight("C", "H", 1000);addFlight("D", "C", 1000);addFlight("E", "H", 1500);}private void databaseGood() // 最理想的情况,A to B{addFlight("A", "B", 500);}private void databaseLong()// 不理想的数据分布, A to J{addFlight("A", "B", 1500);addFlight("A", "I", 1500);addFlight("I", "J", 1500);addFlight("B", "C", 1500);addFlight("B", "A", 1500);addFlight("C", "D", 1500);addFlight("C", "B", 1500);addFlight("D", "C", 1500);}private void databaseLong2()// 不理想的数据分布, A to J{addFlight("A", "B", 1500);addFlight("A", "I", 1500);addFlight("I", "J", 1500);addFlight("B", "A", 1500);// --addFlight("B", "C", 1500);// --addFlight("C", "B", 1500);// --addFlight("C", "D", 1500);// --addFlight("D", "C", 1500);}}