📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
跳转到指定楼层
上一主题 下一主题
收起左侧

求教bfs/dfs

🔗
Latte 2016-4-11 08:51:59 | 只看该作者
全局:
本帖最后由 Latte 于 2016-4-11 08:56 编辑

我感觉在tree都还容易理解,但在graph里我就很头疼,分享一个题目吧,昨天OA的一个题,隔壁版有人分享过,我规定时间没做出来Input是这样的:在input.txtfile里:
A F
A : B C
B : C D E
C : F
D : F

第一行字母代表start和end,后面是node和node相邻的path/node
求A -> F所有path,很蛋疼的是网上和书里好多例子都是int代表的。我很弱希望牛人指点轻拍,BFS构建所有A出发的path,一旦发现终点是F,立马加入final list里面
不知是否需要一个纪录node是否visit的list
  1. static List<String> parseLines(List<String> lines) {
  2.            
  3.                 HashMap<String, ArrayList<String>> gh = new HashMap<String, ArrayList<String>>();
  4.                
  5.             String node = lines.get(0);
  6.             String[] nodeArray = node.split(" "); //[A, E]
  7.             String startNode = nodeArray[0];
  8.             String endNode = nodeArray[1];

  9.             // create the graph as a hashmap[A: [B, C, D]]
  10.             for (String line : lines.subList(1, lines.size()-1)) {
  11.                     String[] list = line.split(" : ");
  12.                     ArrayList<String> neighbor = new ArrayList<String>(Arrays.asList(list[1].split(" ")));

  13.            
  14.             List<String> tempPaths = new ArrayList<String>();
  15.             // initialize a paths array ["A"]
  16.         tempPaths.add(0, startNode);
  17.            
  18.             List<String> finalPaths = new ArrayList<String>();
  19.            
  20.             int n = gh.keySet().size();
  21.            
  22.             // not sure if needs to track if the node has been visited
  23.             HashMap<String, Boolean> visitMap = new HashMap<String, Boolean>();


  24.         // Create a queue for BFS
  25.         LinkedList<String> queueBFS = new LinkedList<String>();

  26.         // Mark the current node as visited and enqueue it
  27.         visitMap.put(startNode, true);
  28.         queueBFS.add(startNode);

  29.         
  30.         while (queueBFS.size() > 0) {
  31.                
  32.                 // get the node in the queue(head of list)
  33.                 String polled = queueBFS.poll();
  34.                
  35.                 // get the neighbor(ArrayList) of this node
  36.                 ArrayList<String> neighbor = gh.get(polled);
  37.                
  38.                 for (int i = 0; i < tempPaths.size(); i++) {
  39.                         if (neighbor == null) {
  40.                                 break;
  41.                         }
  42.                         String path = tempPaths.get(i);
  43.                         // find the path that ends with current node
  44.                         if (path.substring(path.length() -1).equals(polled)) {
  45.                                                                
  46.                                 for (String thisNode: neighbor) {
  47.                                           
  48.                                     String newPath = path.concat(thisNode);
  49.                                         tempPaths.add(newPath);
  50.                                        
  51.                                         // if found an required path like "start----end", add it to final list
  52.                                         // and remove it from temp list
  53.                                         if (newPath.substring(newPath.length() - 1).equals(endNode)) {
  54.                                                 finalPaths.add(newPath);
  55.                                                 tempPaths.remove(newPath);
  56.                                         }
  57.                                        
  58.                             }
  59.                                
  60.                                 // after update the path to new path "A" -> "AB", AC", remove "A"?
  61.                                 tempPaths.remove(path);
  62.                                
  63.                         } // end if
  64.                        
  65.                 } // end for
  66.                
  67.                 // after all is done, add neighbors to queue
  68.                 // Can't figure out how to do this in the above loop without repeating
  69.                 if (neighbor != null) {
  70.                         for (String currentNode: neighbor) {
  71.                                     queueBFS.add(currentNode);
  72.                     }
  73.                 }       
  74.         }
  75.            
  76.             return finalPaths;
  77.     }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表