要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 983|回复: 8
收起左侧

[CareerCup] 问一下CC150里面的DFS代码

[复制链接] |试试Instant~ |关注本帖
MTC 发表于 2014-11-29 21:02:40 | 显示全部楼层 |阅读模式

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

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

x
  1. public static void DFS(Node root){

  2. if(root==null) return;//不是递归的终止条件吧,是检查root是否为空的吧?
  3. visit(root);
  4. root.visited=true;
  5. for(Node n:root.adjacent){
  6. if(n.visited==false){

  7. search(n);
  8. }


  9. }


  10. }
复制代码
if(root==null) return;
不是递归的终止条件吧,是检查root是否为空的吧?递归的终止条件应该是root.visited==true吧,图怎么可能会有节点的adjcent为空的情况呢?

上一篇:Intersection of Two Linked Lists分享一种和答案不同的简单解法
下一篇:大家说CC150刷题指的是什么?
头像被屏蔽
kinslayer 发表于 2014-11-29 23:35:14 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
 楼主| MTC 发表于 2014-11-30 10:20:39 | 显示全部楼层
kinslayer 发表于 2014-11-29 23:35
root.visited==true就不进递归了啊 它这是全部for都执行完一遍就结束了

第三行可以删掉吗?
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-12-2 11:18:48 | 显示全部楼层
当你第一次调用dfs的时候,那个root可能为空
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-12-2 12:09:04 | 显示全部楼层
1guangnian 发表于 2014-12-2 11:18
当你第一次调用dfs的时候,那个root可能为空

对啊,就是增加程序的健壮性的不?不是递归终止返回上一层的条件
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-12-2 15:37:29 | 显示全部楼层
MTC 发表于 2014-12-2 12:09
对啊,就是增加程序的健壮性的不?不是递归终止返回上一层的条件

如果node.adjacent里面不包含null节点,第三行确实意义不大,可以在调用dfs之前就判断
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2014-12-3 00:10:18 | 显示全部楼层
本来这是recursive的写法,结果把函数名search改成DFS了,破坏了原有的结构
if (root == null) return; 避免访问空节点
root.visited = true只是一个flag,标记一下已经访问过的节点,避免重复访问
回复 支持 反对

使用道具 举报

 楼主| MTC 发表于 2014-12-3 10:33:01 | 显示全部楼层
Freetymekiyan 发表于 2014-12-3 00:10
本来这是recursive的写法,结果把函数名search改成DFS了,破坏了原有的结构
if (root == null) return; 避 ...

不好意思,函數名笔误了。。。不过图会有adjecent为空的情况吗?不可能啊,除非他是孤立的,否则递归根本不能结束
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2014-12-3 11:51:03 | 显示全部楼层
MTC 发表于 2014-12-2 21:33
不好意思,函數名笔误了。。。不过图会有adjecent为空的情况吗?不可能啊,除非他是孤立的,否则递归根本 ...

是的 每个节点都访问到了就结束了
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 09:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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