前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >深度优先搜索(DFS)

深度优先搜索(DFS)

作者头像
刘开心_1266679
发布2019-02-14 15:34:13
1.2K0
发布2019-02-14 15:34:13
举报
文章被收录于专栏:开心的学习之路

深度优先搜索属于图算法的一种,英文缩写为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

分析:具体过程如图

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015年03月12日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档