一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1397|回复: 10
收起左侧

[算法题] 求教bfs/dfs

[复制链接] |试试Instant~ |关注本帖
一回头的温柔 发表于 2016-3-6 18:21:39 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 一回头的温柔 于 2016-3-6 18:22 编辑

楼主被同一个类型的题卡住了。。。说起来都是BFS/DFS, 但就感觉不太会把代码写出了。有人愿意分享一下代码吗,伪代码也行,从怎么定义节点,怎么DFS/Bfs,因为这种题还挺典型的,不会写有点慌。。。(一下都是Google的原题)
1.第三轮是一个看起来像是老墨或者老印的人,问了一个运动场里面要求找到一个点离三个器材加起来距离最近的题目,器材周围有障碍物,用bfs解决,问了一些follow up, 也都没问题。
2.给一个二维矩阵,里面有几个点是守卫,求到所有守卫距离最远的点。
ChTimTsubasa 发表于 2016-3-7 02:39:31 | 显示全部楼层
都是遍历相邻节点 bfs是用栈 dfs是队
回复 支持 0 反对 1

使用道具 举报

gegeyongfu 发表于 2016-3-7 03:26:44 | 显示全部楼层
ChTimTsubasa 发表于 2016-3-7 02:39
都是遍历相邻节点 bfs是用栈 dfs是队

是不是说反了
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-3-7 03:50:27 | 显示全部楼层
说反了,其实dfs还可以用recursion,然后基本所有的bfs的题目都可以用dfs写出来
回复 支持 反对

使用道具 举报

 楼主| 一回头的温柔 发表于 2016-3-7 07:06:41 | 显示全部楼层
qiuxuxing007 发表于 2016-3-7 03:50
说反了,其实dfs还可以用recursion,然后基本所有的bfs的题目都可以用dfs写出来

能挑一题给点代码么,我知道用dfs/bfs...
回复 支持 反对

使用道具 举报

download1992 发表于 2016-3-7 13:43:26 | 显示全部楼层
简单来说就是先把根节点加入队或者栈 然后不断地从队(bfs)或者栈(dfs)里面取节点并且加入取出节点的子节点
回复 支持 反对

使用道具 举报

 楼主| 一回头的温柔 发表于 2016-3-7 15:30:50 | 显示全部楼层
download1992 发表于 2016-3-7 13:43
简单来说就是先把根节点加入队或者栈 然后不断地从队(bfs)或者栈(dfs)里面取节点并且加入取出节点的子 ...

dfs和bfs的原理我都懂,求根据以上两个题,给一点代码
回复 支持 反对

使用道具 举报

download1992 发表于 2016-3-7 16:12:45 | 显示全部楼层
本帖最后由 download1992 于 2016-3-7 16:29 编辑

就是对每个点用bfs啊 然后求和找和最大最小的就Ok了 不知道你知道了bfs原理还有哪块不懂吗?
图上node包含坐标 visitlabel(表示有没有visit过) step(记录从初始点到这一点的距离) type(表示可通过,器材,还是障碍)

然后按照bfs做就行了啊 取节点加子节点(一般加上下左右,这里要判断类型,并且判断是不是到了边界) 子节点step=父节点step+1 做到所有possible nodes都遍历过就好了啊
回复 支持 反对

使用道具 举报

gracia_g 发表于 2016-3-11 13:11:17 | 显示全部楼层
个人感觉,你比较一下图算法里有BFS和DFS思想的不同算法就有个大概感觉了。比如单源最短路的Dijkstra就是BFS,就是从一个节点开始,一层一层的向外扩张。求无向图是否有环的方法就可以用DFS。
刚刚和朋友讨论,他说,**一般来说**,求是否存在解的时候多用DFS,求最优解的时候多用BFS,这个说法基本和上面的两个例子也比较呼应。总之多复习复习图算法是很有用的。
回复 支持 反对

使用道具 举报

会踢球的哈士奇 发表于 2016-3-23 23:39:25 | 显示全部楼层
最近一直在搞树的问题, 对树的BFS 和 DFS ,  我个人有一些自己的理解

DFS相对难一些 对树来说DFS一般用recursion 来解决, DFS 在树里面还有细分的两种方法  top down, bottom up.  top down就是从root开始每一次做你该做的事请然后向下走走到叶子然后就可以递归回来了,   bottom up是刚开始要先走到叶子节点, 然后根据叶子信息来计算root 然后一层一层向上走到root。

BFS我一般都直接用Queue 非递归感觉要简单一些

一家之言, 也希望大家指出我想的不对的地方

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 05:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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