3回答

liuyubobobo

2018-11-14

已采纳

如果你初始调用的是dfs(1)，0肯定是从1遍历过去的。

如果如你所说，从1到0，0已经访问过了的话，肯定之前从别的节点访问过0。你说"然而在if语句中 [visited[0] 已经被遍历过"，0是在哪里遍历的？在debug一下，看看什么时候visited[0]设的true？（我怀疑你的初始调用是dfs(0)，所以一上来0就遍历过了。）

可以在这个函数中添加各种cout，来查看函数的行为，比如：

void dfs(int v) {
    cout << "访问" << v << "!" << endl;
    visited[v] = true;
    cout << "将 visited[" << v << "] 设为true" << endl;
    
    id[v] = ccount;
    
    for(int i : G.adj(v)) {
        cout << "从" << v << "到" << i << endl;
        if(!visited[i])
            cout << i << "没有访问过！准备访问" << i << endl;
            dfs(i);
            cout << "从" << v << "到" << i << "遍历完，回到" << v << endl；
        }
        else{
            cout << i << "已经访问过！" << endl;
        }
        
    cout << v << "的所有相邻节点已经遍历完毕！" << endl;
}

再通过debug，看看上面的输出是什么顺序如何一句一句输出出来的？

如果有必要的化，让图更简单一些，节点更少，看能不能理解？

加油！：）

0

2

the__sky123

非常感谢！

2018-11-14

共2条回复

the__sky123

提问者

2018-11-14

老师你明白我的意思了吗？ 我的意思是从22行跳到17行，v就从1变成0了 ，不太懂这是什么原理

0

1

liuyubobobo

他们在不同的dfs调用中，而不是一个dfs调用。你可以理解成他们在不同的函数里。a调用b，b执行完以后，会回到a。递归同理，只不过是a调用a而已，后一个a执行完以后，会回到前一个a。

2018-11-14

共1条回复

the__sky123

提问者

2018-11-14

这个时候是1，但

在这之后v就变成0了，我是不太懂，dfs里没有对v的赋值操作，而且如果此点被访问过后就不会再访问了，所以在代码中也没有看到对v的操作，但v却一直在变化

0

2

liuyubobobo

你对递归的理解可能还有欠缺。这个课程由于课程定位的原因，并没有对递归机制进行详细讲解。这个课程的课程定位参考：https://coding.imooc.com/learn/questiondetail/16248.html 我建议如果你购买了我的《玩转算法面试》课程，仔细学习一遍第五章，再回头看这里是不是能理解：）加油！

2018-11-14

共2条回复