深度优先搜索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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2017.9.17校内noip模拟赛解题报告

预计分数:100+60+60=220 实际分数:100+60+40=200 除了暴力什么都不会的我。。。。。 T1 2017.9.17巧克力棒(chocolat...

42170
来自专栏炉边夜话

考场安排---图的着色原理之运用

试设计一算法,当给定一个图时G=(V,E),|V|=n,(Vi,Vj)ЄE,当且仅当有一个同学选了课程i和课程j,试给出一个考试安排方案N1,N2,N3…Nk,...

16710
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

教程 OpenGL ES入门教程1-Tutorial01-GLKit OpenGL ES入门教程2-Tutorial02-shader入门 OpenGL E...

36150
来自专栏生信技能树

二代测序数据拼接之原理篇

前前后后接触了一些基因组和转录组拼接的工作,而且后期还会持续进行。期间遇到了各种各样莫名其妙的坑,也尝试了一些不同的方法和软件,简单做一个阶段性小结,本篇是原理...

1.7K50
来自专栏数据结构与算法

2018.7.30考试

题意:给出两棵树,问在两棵树中任意删除一条边后$1$号节点所在集合的元素相同的方案

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

BZOJ1059: [ZJOI2007]矩阵游戏(二分图匹配)

  小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N

10320
来自专栏大数据文摘

动图,用Python追踪NBA球员的运动轨迹

74940
来自专栏老马说编程

(34) 随机 / 计算机程序的思维逻辑

随机 本节,我们来讨论随机,随机是计算机程序中一个非常常见的需求,比如说: 各种游戏中有大量的随机,比如扑克游戏洗牌 微信抢红包,抢的红包金额是随机的 北京购...

27560
来自专栏逍遥剑客的游戏开发

玻璃效果

13560
来自专栏人人都是极客

GPU渲染之OpenGL的GPU管线

GPU渲染流水线,是硬件真正体现渲染概念的操作过程,也是最终将图元画到2D屏幕上的阶段。GPU管线涵盖了渲染流程的几何阶段和光栅化阶段,但对开发者而言,只有对顶...

20630

扫码关注云+社区

领取腾讯云代金券