深度优先搜索

黄蕊小白花

         深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的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];
   6 k+ r- e' Z4 a* Q" Q
7.     int n,k;
   
8. 
   
9. //已经从前i项得到了和sum，然后对于i项之后的进行分支
   * ^7 g! m6 H) Y6 Z7 u6 Z
10. bool dfs(int i,int sum)
    / {- K5 z4 }2 [9 [/ q
11. {
    
12.     //如果前n项都计算过了 ，则返回sum是否与k相等
    
13.     if(i==n)
    ( X3 l- P: L$ X
14.     {
    
15.         return sum==k;
    * b+ q% w. n. D1 b* T
16.      }
      M7 s* k; H  n( j+ O
17. 
    % t/ a/ X, ]3 b- k
18.     //不加上a[i]的情况的分支
    - \6 }% K7 t' c5 ]  K4 \
19.     if(dfs(i+1,sum))
    5 |7 e9 w  R3 P* l7 n" v
20.     {
    
21.         return true;
    + q' ?9 h3 J1 M6 t2 Z; j/ n
22.     }
    
23.     //加上a[i]的情况的分支
    
24.     //if(dfs(i+1,sum+a[i+1]))
    
25.     if(dfs(i+1,sum+a[i]))
    2 {9 Y& x+ l, V2 C+ j
26.     {
    ) q# F5 ^, H. r; s+ `9 V! `
27.         return true;
    
28.     }
    # A( t) ^$ z0 C( ^/ t
29. 
    8 h; B7 [1 n( G/ x5 k& r
30.     //无论是否加上a[i]都不能凑成k就返回false
    
31.     return false;
    
32. }
    
33. void solve()
    7 V7 q7 O  b. r  a* U8 ?
34. {
    5 K5 N- N" \4 ^1 |% q
35.      //if(dfs(1,0))
    
36.      if(dfs(0,0))
    - ~$ j2 S5 d  Q0 Y. a' U
37.     {
    
38.          cout<<"Yes"<<endl;
    
39.     }
    
40.      else
    ; h# |$ D- A  V3 x- e/ A7 j/ N" [
41.      {
    
42.          cout<<"No"<<endl;
    
43.      }
    
44. }
    % [" Q( A) @2 Q/ S/ \
45. int main(void)
    
46. {
    2 u1 Q" o+ s) R; p9 i1 e
47.     cin>>n;
    
48.     int i,temp;
    " x* Q4 C1 D3 Z' D" k3 B
49.     //for(i=1;i<=n;i++)
    0 L( t- U- p  L6 Q  e* p$ F' _
50.     for(i=0;i<n;i++)
    
51.     {
    
52.         cin>>temp;
    
53.         a[i]=temp;
    
54.     }
    
55.     cin>>k;
    + k- @( j, V/ a! d
56. 
    4 U6 w& k7 Y/ Y6 x1 `" u
57.     solve();
    
58. 
    ! c1 K% w4 B, v: y7 y* |
59.     return 0;
    - U3 u- E( z& e& l* C6 ~: \
60. }

复制代码

+ b: n/ x- A" Z7 x: [8 i% q  j) n% A

( z* X$ f% Q2 l
3 L# Q9 a) ^: V- y# }7 k