深度优先搜索

黄蕊小白花

         深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。
用c++更好地实现

1. //C++深度优先搜索(递归树模拟)
   
2. #define _CRT_SECURE_NO_WARNINGS
   
3. #include <iostream>
   
4. #define MAX_N 1000
   
5. using namespace std;
   
6.     int a[MAX_N];
   
7.     int n,k;
   
8. 
   
9. //已经从前i项得到了和sum，然后对于i项之后的进行分支
   
10. bool dfs(int i,int sum)
    
11. {
    
12.     //如果前n项都计算过了 ，则返回sum是否与k相等
    
13.     if(i==n)
    
14.     {
    
15.         return sum==k;
    
16.      }
    
17. 
    
18.     //不加上a[i]的情况的分支
    
19.     if(dfs(i+1,sum))
    
20.     {
    
21.         return true;
    
22.     }
    
23.     //加上a[i]的情况的分支
    
24.     //if(dfs(i+1,sum+a[i+1]))
    
25.     if(dfs(i+1,sum+a[i]))
    
26.     {
    
27.         return true;
    
28.     }
    
29. 
    
30.     //无论是否加上a[i]都不能凑成k就返回false
    
31.     return false;
    
32. }
    
33. void solve()
    
34. {
    
35.      //if(dfs(1,0))
    
36.      if(dfs(0,0))
    
37.     {
    
38.          cout<<"Yes"<<endl;
    
39.     }
    
40.      else
    
41.      {
    
42.          cout<<"No"<<endl;
    
43.      }
    
44. }
    
45. int main(void)
    
46. {
    
47.     cin>>n;
    
48.     int i,temp;
    
49.     //for(i=1;i<=n;i++)
    
50.     for(i=0;i<n;i++)
    
51.     {
    
52.         cin>>temp;
    
53.         a[i]=temp;
    
54.     }
    
55.     cin>>k;
    
56. 
    
57.     solve();
    
58. 
    
59.     return 0;
    
60. }

复制代码