首页 > 代码库 > 最易懂的DFS算法

最易懂的DFS算法

这是世界上最易懂的算法,呵呵,来自啊哈算法。

#include <iostream>using namespace std; int a[10],book[10],n;int total;void dfs(int step) //step表示站在第几个盒子面前{    if(step==n+1) //如果站在第n+1个盒子面前,则表示前n个盒子已经放好扑克牌    {   //输出一种排列(1-n号盒子中的扑克牌编号)        for(int i=1;i<=n;i++)            cout<<a[i];        cout<<endl;        total++;        return; //返回之前的一步(最近一次调用DFS函数的地方)    }
//此时站在第step个盒子面前,应该放哪张牌呢?
//按照1、2、3...n的顺序一一尝试
for(int i=1;i<=n;i++)
//判断扑克牌是否还在手上
if(book[i]==0) //book[i]等于0表示i号扑克牌在手上 { //开始尝试使用扑克牌i a[step]=i; //将i号扑克牌放入到第step个盒子中 book[i]=1; //将book[i]设为1表示i号扑克牌已经不在手上
//第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前 dfs(step
+1); //这里通过函数的递归调用来实现 book[i]=0; //这是非常重要的一步,一定要将刚才尝试的扑克牌收回才能进行下一步的尝试 }}int main(){ n=4; dfs(1); cout<<"count:"<<total<<endl; return 0;}

 

最易懂的DFS算法