深度优先搜索DFS(一)

从起点出发,走过的点做标记,发现没有走过的点,就随意挑一个往前走,走不了就回退,此种路径搜索策略就称为“深度优先搜索(Depth First Search)”。

       其实称为“远度优先搜索”更容易理解。因为这种策略能往前走一步就往前走一步,总是试图走的更远,所谓远近(深度),其实是以距离起点来衡量的。

//判断从v出发能否走到终点 
 bool DFS(v)
 {
         if(v为终点)
                return true;
         if(v为旧点)
                return false;
         将v标记为旧点;
         对和v相邻的每个节点u
         {
                if(DFS(u) == true)
                        return true;   
         } 
         return false;
 } 
 int main()
 {
         将所有点都标为新点;
         起点 = x;
         终点 = y;
         cout<<Dfs(起点);
 }//
Node path[Max_len];//Max_len取节点总数即可
 int depth;
 bool DFS(v)
 {
         if(v为终点)
         {
                path[depth] = v;
                return true;
         } 
         if(v为旧点)
                return false;
         将v标记为旧点;
         path[depth] = v;
         ++depth;
         对和v相邻的每个节点u
         {
                if(DFS(u) == true)
                        return true;
         } 
         --depth;
         return false;
 } 
 int main()
 {
         将所有的点都标记为新点;
         depth = 0;
         if(DFS(起点))
         {
                for(int i = 0;i <= depth;i++)
                {
                        cout<<depth[i]<<endl;
                } 
         } 
 }
//深度优先遍历图上所有节点
 DFS(v)
 {
         if(v是旧点)
                return;
         将v标记为旧点;
         对和v相邻的所有节点u
         {
                DFS(u);
         } 
 } 
 int main()
 {
         将所有的点都标为新点;
         while(在图中能找到新点k)
         {
                DFS(k);
         } 
 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个...

481
来自专栏calmound

hdu 1850 Being a Good Boy in Spring Festival

太开心了,这是我第一道自己想出来的利用二进制的做法把博弈做出来的,good!!! 题意:一般的博弈,给你n堆,一次只能取一堆中的任意个,求先手若想获胜有多少可行...

3055
来自专栏深度学习之tensorflow实战篇

tensorflow之tf.placeholder 与 tf.Variable区别对比

二者的主要区别在于 Variable:主要是用于训练变量之类的。比如我们经常使用的网络权重,偏置。 值得注意的是Variable在声明是必须赋予初始值。在训...

3064
来自专栏函数式编程语言及工具

泛函编程(28)-粗俗浅解:Functor, Applicative, Monad

    经过了一段时间的泛函编程讨论,始终没能实实在在的明确到底泛函编程有什么区别和特点;我是指在现实编程的情况下所谓的泛函编程到底如何特别。我们已经习惯了传统...

1986
来自专栏desperate633

LintCode 最大正方形题目分析代码

样例 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 返回 4

642
来自专栏数据结构与算法

BZOJ4195: [Noi2015]程序自动分析(并查集)

考虑一个约束满足问题的简化版本:假设x1,x2,x3...代表程序中出现的变量,给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件,请判定是否可以分别...

652
来自专栏我是攻城师

十大算法,让你轻松进阶高手

3507
来自专栏章鱼的慢慢技术路

《算法图解》第八章_贪婪算法_集合覆盖问题

1766
来自专栏Petrichor的专栏

leetcode: 62. Unique Paths

842
来自专栏深度学习那些事儿

pytorch中autograd以及hook函数详解

有些公式为图片,如果这个页面加载不出来,请看这里:https://oldpan.me/archives/pytorch-autograd-hook

86210

扫码关注云+社区