一亩三分地论坛

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

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

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

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

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

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

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为空的情况呢?
头像被屏蔽
kinslayer 发表于 2014-11-29 23:35:14 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| 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为空的情况吗?不可能啊,除非他是孤立的,否则递归根本 ...

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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