dfs函数中的问题

Question

void dfs(int v) {
		visited[v] = true;
		id[v] = ccount;
		
		for(int i : G.adj(v)) {
			if(!visited[i])
				dfs(i);
		}
	}

还是不能理解这个方法，我在debug时，就使用的演示中的图，在对1进行迭代，找到与1相连的是[ 0] ,然而在if语句中 [visited[0] 已经被遍历过，所以不进入if循环，在if外没有任何代码，在下次循环时，debug中显示v = 0 ， 请问v是如何完成回溯，从1跳回到0的

Answer 1

liuyubobobo 2018-11-14 19:02:07

如果你初始调用的是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，看看上面的输出是什么顺序如何一句一句输出出来的？

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

加油！：）

• 提问者 the__sky123 #1

  我是不懂这个dfs的原理...v遍历完1是如何回到0的

• 提问者 the__sky123 #2

  非常感谢！

Answer 2

提问者 the__sky123 2018-11-14 22:09:17

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

• liuyubobobo #1

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

Answer 3

提问者 the__sky123 2018-11-14 22:02:00

这个时候是1，但

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

• liuyubobobo #1

  v是一个参数！你调dfs(0)的时候，v就是0，你调dfs(i)的时候，调用下一层dfs，v传的就是i对应的值。当一层dfs调用完以后，会回到上一层dfs！dfs是一个递归函数，v的值不同，其实是在不同的函数调用中！

• liuyubobobo #2

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