问一下CC150里面的DFS代码

1. public static void DFS(Node root){
   
2. 
   
3. if(root==null) return;//不是递归的终止条件吧，是检查root是否为空的吧？
   
4. visit(root);
   
5. root.visited=true;
   
6. for(Node n:root.adjacent){
   
7. if(n.visited==false){
   
8. 
   
9. search(n);
   
10. }
    
11. 
    
12. 
    
13. }
    
14. 
    
15. 
    
16. }

复制代码

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

kinslayer 发表于 2014-11-29 23:35
root.visited==true就不进递归了啊 它这是全部for都执行完一遍就结束了

第三行可以删掉吗？

当你第一次调用dfs的时候，那个root可能为空

1guangnian 发表于 2014-12-2 11:18
当你第一次调用dfs的时候，那个root可能为空

对啊，就是增加程序的健壮性的不？不是递归终止返回上一层的条件

MTC 发表于 2014-12-2 12:09
对啊，就是增加程序的健壮性的不？不是递归终止返回上一层的条件

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

本来这是recursive的写法，结果把函数名search改成DFS了，破坏了原有的结构
if (root == null) return; 避免访问空节点
root.visited = true只是一个flag，标记一下已经访问过的节点，避免重复访问

Freetymekiyan 发表于 2014-12-3 00:10
本来这是recursive的写法，结果把函数名search改成DFS了，破坏了原有的结构
if (root == null) return; 避 ...

不好意思，函數名笔误了。。。不过图会有adjecent为空的情况吗？不可能啊，除非他是孤立的，否则递归根本不能结束

MTC 发表于 2014-12-2 21:33
不好意思，函數名笔误了。。。不过图会有adjecent为空的情况吗？不可能啊，除非他是孤立的，否则递归根本 ...

是的 每个节点都访问到了就结束了