深度优先搜索

黄蕊小白花

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

1. //C++深度优先搜索(递归树模拟)
   $ Z% @+ _7 M  Y- |5 v
2. #define _CRT_SECURE_NO_WARNINGS
   . \) D5 q4 m& n. j7 m# l5 J
3. #include <iostream>
   
4. #define MAX_N 1000
   * c, y- z# e& Q3 ]% Z* U
5. using namespace std;
   3 g& E6 Z7 `; |9 k
6.     int a[MAX_N];
   6 ~' ^' u. I  Q- Y, q7 Z
7.     int n,k;
   5 P  R. V. C( L2 y4 ]$ m
8. 
   
9. //已经从前i项得到了和sum，然后对于i项之后的进行分支
   
10. bool dfs(int i,int sum)
    
11. {
    3 S$ o8 x) T. W8 {. l
12.     //如果前n项都计算过了 ，则返回sum是否与k相等
    
13.     if(i==n)
    
14.     {
    
15.         return sum==k;
    % I7 h  n6 Q+ j5 \
16.      }
    9 D8 ~) ~0 [2 l. |3 L
17. 
    
18.     //不加上a[i]的情况的分支
    7 K7 j+ {. W& w# c+ u$ s
19.     if(dfs(i+1,sum))
    
20.     {
    
21.         return true;
    % W# r9 j9 u( ]. M7 V
22.     }
    7 }6 l. }2 w0 ^6 Z5 n
23.     //加上a[i]的情况的分支
      @. V* J3 M% B( v: O0 k
24.     //if(dfs(i+1,sum+a[i+1]))
    5 }4 R. V, M& O
25.     if(dfs(i+1,sum+a[i]))
    
26.     {
    7 q2 {0 u& s$ e+ f$ I4 K! d
27.         return true;
    # ^1 G4 ]) Z/ T# Z' [( v  p% O
28.     }
    
29. 
    
30.     //无论是否加上a[i]都不能凑成k就返回false
    
31.     return false;
    
32. }
    + N0 V. v5 n! E: e' D. p
33. void solve()
    3 l0 W; x5 T4 ~: f; ?5 i! A
34. {
    
35.      //if(dfs(1,0))
    3 f( U% b8 n9 b% w6 U/ W
36.      if(dfs(0,0))
    1 u" X) h- S5 C+ Z- ?" c; a4 Y
37.     {
    
38.          cout<<"Yes"<<endl;
    
39.     }
    
40.      else
    & m5 y  C$ w2 \
41.      {
    # {3 |2 K8 K* e7 ^* O( L
42.          cout<<"No"<<endl;
    
43.      }
    
44. }
    7 v+ s6 t4 S1 F
45. int main(void)
    8 O) N1 ?: ^, U4 a/ o
46. {
    5 Y- q6 [( X: ?- ?5 z
47.     cin>>n;
    
48.     int i,temp;
    
49.     //for(i=1;i<=n;i++)
    % x6 I0 U0 u- Y
50.     for(i=0;i<n;i++)
    
51.     {
    5 c  D( g# {7 T- l7 Y
52.         cin>>temp;
    
53.         a[i]=temp;
    
54.     }
    
55.     cin>>k;
    
56. 
    # B) ~9 c, D- @& S% c. |6 p) _# M
57.     solve();
    ) W' [$ W2 g5 l5 [; U; L
58. 
    
59.     return 0;
    
60. }

复制代码

) ~2 T, A7 \  \$ P6 D( G' q
' [3 H4 l8 {3 t
$ l7 Y1 w6 Q8 |4 P' {$ }