动象论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 70 | 回复: 0

深度优先搜索

[复制链接]

12

主题

94

帖子

227

积分

清正廉明~版主

风纪委员

Rank: 16Rank: 16Rank: 16Rank: 16

积分
227

论坛官方最佳新人活跃会员

发表于 2020-7-18 11:42:56 | 显示全部楼层 |阅读模式
         深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的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. //已经从前i项得到了和sum,然后对于i项之后的进行分支
  9. bool dfs(int i,int sum)
  10. {
  11.     //如果前n项都计算过了 ,则返回sum是否与k相等
  12.     if(i==n)
  13.     {
  14.         return sum==k;
  15.      }

  16.     //不加上a[i]的情况的分支
  17.     if(dfs(i+1,sum))
  18.     {
  19.         return true;
  20.     }
  21.     //加上a[i]的情况的分支
  22.     //if(dfs(i+1,sum+a[i+1]))
  23.     if(dfs(i+1,sum+a[i]))
  24.     {
  25.         return true;
  26.     }

  27.     //无论是否加上a[i]都不能凑成k就返回false
  28.     return false;
  29. }
  30. void solve()
  31. {
  32.      //if(dfs(1,0))
  33.      if(dfs(0,0))
  34.     {
  35.          cout<<"Yes"<<endl;
  36.     }
  37.      else
  38.      {
  39.          cout<<"No"<<endl;
  40.      }
  41. }
  42. int main(void)
  43. {
  44.     cin>>n;
  45.     int i,temp;
  46.     //for(i=1;i<=n;i++)
  47.     for(i=0;i<n;i++)
  48.     {
  49.         cin>>temp;
  50.         a[i]=temp;
  51.     }
  52.     cin>>k;

  53.     solve();

  54.     return 0;
  55. }
复制代码





评分

参与人数 1 +200 收起 理由
admin + 200 很给力!

查看全部评分

本帖被以下淘专辑推荐:


tel:181 5707 6602
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

 QQ 手机版小黑屋网站地图

GMT+8, 2021-8-4 02:12 Processed in 0.226734 second(s), 27 queries .

CopyRight © 2020-2021 DongXiang BBS. All Rights Reserved.

ICP备案号:粤ICP备17035028号-1

Sectigo签章 MySSL签章

快速回复 返回顶部 返回列表