说起回家,路途漫漫,行李满满,尤其我等村里交通不发达的地方,可能连直达的票都没有,虽说条条大陆通罗马,但毕竟还是想找个换乘最少的路线,毕竟谁不想回家更轻松点呢(*^_^*),下面就是我回家的所有路线。
思路很简单,先找起点看是否能到,不能到的话,看起点能到的点的下一步是否能到
话不多说,撸代码:
public static void main(String[] args) { HashMap<String,List<String>> data = new HashMap<String, List<String>>(); List<String> list1 = new ArrayList<String>(); data.put("起点",list1); list1.add("A"); list1.add("B"); List<String> list2 = new ArrayList<String>(); data.put("A",list2); list2.add("终点"); List<String> list3 = new ArrayList<String>(); data.put("B",list3); list3.add("A"); list3.add("终点"); query(data,"终点","起点"); } public static void query(Map<String,List<String>> data, String queryValue, String start){ if(data==null || queryValue ==null){ return; } Queue<String> queue = new LinkedList<String>(); Map quaryLog = new HashMap(); Map<String,List<String>> routes = new HashMap<String, List<String>>(); queue.offer(start); quaryLog.put(start,""); String parent = null; while (!queue.isEmpty()){ parent = queue.poll(); List<String> values = data.get(parent); for(String value:values){ List<String> r = new ArrayList<String>(); if(routes.containsKey(parent)){ r.addAll(routes.get(parent)); } r.add(parent); routes.put(value,r); if(queryValue.equals(value)){ routes.get(value).add(value); System.out.println(routes.get(value)); return; } if(!quaryLog.containsKey(value)){ queue.offer(value); quaryLog.put(value,""); } } } return ; }