专栏首页开心的学习之路深度优先搜索(DFS)

深度优先搜索(DFS)

深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.

算法:

1、构造一个有根构成的单元素栈S;

2、If Top(S) 是目标节点 Then 停止;

3、Pop(S), 把Top(S)的所有子节点压入栈顶;

4、If S空 Then 失败 Else goto 2.

举例:

求解子集和问题

------输入:S = {7, 5, 1, 2, 10}

------输出:是否存在S'含于S,使得Sum(S') = 9

分析:具体过程如图

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基础练习 数列排序

      第一行为一个整数n。   第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    刘开心_1266679
  • 线性结构------线性表(二)

        如果要对链表进行插入删除操作,用顺序结构需要找到目标位置然后移动大量元素,复杂度为O(n),此时就需要考虑线性表的链式存储结构。

    刘开心_1266679
  • 广度优先搜索(BFS)

    广度优先搜索(BFS)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。

    刘开心_1266679
  • Codeforces 460C

    比较裸的二分,但是比赛的时候脑抽,用树状数组瞎搞过了,但是边界条件没注意让hack了。 后来看到有人写了很简单的版本,又过了一遍,提醒一下自己不能忘记基本算法。...

    triplebee
  • udp服务端收发数据流程

    skylark
  • Java与C/C++不同的一些基础知识点

    0. 类与文件 一个 java 文件可以写多个类,每个类里面可以有main函数,一个java文件里面只能有一个 public 类,此时 java 文件的命名只...

    s1mba
  • 最详细的CentOS 6与7对比(三):性能测试对比

    如图所示,本次一共做了7项,其中有2项是CentOS 6与7基本一致,另外5项都是CentOS 7明显胜出,因此可以得出结论:CentOS 7的性能比CentO...

    小慢哥Linux运维
  • 5分钟带你快速入门和了解 OAM Kubernetes

    OAM 的全称为开放应用模型(Open Application Model),由阿里巴巴宣布联合微软共同推出。

    落跑架构师M
  • 复杂业务场景下如何进行iOS端自动化测试|洞见

    去年写了一篇《容器化时代对测试的机遇》的文章,提到了一些分布式自动化测试和容器化技术结合的架构设想。但是目前来说,分布式运行并不是难点,亟需解决的问题是针对特殊...

    ThoughtWorks

扫码关注云+社区

领取腾讯云代金券