java的线路求解问题

Question

有向图的广度优先问题；
若是不能有重复节点，提供你一个思路：findRoutes(起始节点, 终止节点, 当前线路) {
    对起始节点的每个下一节点做如下操作: {
        如果节点是终止节点, 则将节点添加到当前线路，加入线路的List中, continue;
        如果节点已在当前线路中, continue;
        否则, 将节点加入当前线路, 以节点为开始节点，终止节点不变，加入该节点后的线路为新的当前线路, 递归获得线路的List;
    }
    返回线路的List;
}

Answer 1

  我知道这思路，我开始就这么设计的，但是就是陷入了死循环中，你看我给出的demo数据，能给出一个实现例子吗，只要demo数据能得出正确结果，那我直接套进去就可以，我写那个研究很久也没研究出来上面地方出现问题，有一点需要提示的是，就是这不是有向的，因为比如1能到4，那么4也能到1，所以这个还必须得排除遍历过的问题。

Answer 2

给个简单的实现；首先是路径类:
class Route {
private List<String> route;

public Route() {
route = new ArrayList<String>();
}

public List<String> getRoute() {
return route;
}

public int length() {
return this.route.size();
}

public void addStop(String stop) {
route.add(stop);
}

public boolean containsStop(String stop) {
return route.contains(stop) ? true : false;
}

public Route copyRoute() {
Route copy = new Route();
for (String stop : route)
copy.addStop(stop);
return copy;
}

public void printRoute() {
System.out.println("----------");
System.out.print("Route length: " + route.size() + "; ");
for (int i = 0; i < route.size(); i++) {
System.out.print(route.get(i));
if (i != route.size() - 1)
System.out.print("-->");
}
}
}
具体实现:
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("1", "3,4");
map.put("2", "3,4");
map.put("3", "1,2,4");
map.put("4", "1,2,3");

Map<String, String[]> newMap = new HashMap<String, String[]>();
Set<String> keySet = map.keySet();
for (String key : keySet) {
String[] stops = map.get(key).split(",");
newMap.put(key, stops);
}


String start = "1";
String end = "4";
Route route = new Route();
route.addStop(start);

List<Route> routeList = findRoute(newMap, start, end, route);
for (Route finalRoute : routeList) {
finalRoute.printRoute();
}
}

public static List<Route> findRoute(Map<String, String[]> map, String start, String end, Route route) {
List<Route> routeList = new ArrayList<Route>();

String[] stops = map.get(start);
for (String nextStop : stops) {
if (nextStop.equals(end)) {
Route temp = route.copyRoute();
temp.addStop(nextStop);
routeList.add(temp);
continue;
} else if (route.containsStop(nextStop)) {
continue;
} else {
Route temp = route.copyRoute();
temp.addStop(nextStop);

List<Route> subRouteList = findRoute(map, nextStop, end, temp);
for (Route subRoute : subRouteList) {
routeList.add(subRoute);
}
}
}
return routeList;
}随便写写，见笑了^_^

Answer 3

  我知道这思路，我开始就这么设计的，但是就是陷入了死循环中，你看我给出的demo数据，能给出一个实现例子吗，只要demo数据能得出正确结果，那我直接套进去就可以，我写那个研究很久也没研究出来上面地方出现问题，有一点需要提示的是，就是这不是有向的，因为比如1能到4，那么4也能到1，所以这个还必须得排除遍历过的问题。谢谢啊！  太忙好几天没上，虽然没试好不好使，但还是非常感谢！