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

相关文章

来自专栏炉边夜话

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

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

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

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

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

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

【BZOJ3203】保护出题人(动态规划,斜率优化)

在最优情况下,肯定是存在某只僵尸在到达重点的那一瞬间将其打死 我们现在知道了每只僵尸到达终点的时间,因为僵尸要依次打死。 所以我们假设血量的前缀和是\(s_...

1655
来自专栏温安适的blog

以回溯解高速公路重建与正序全排列

3716
来自专栏温安适的blog

图论-网络流

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

2018.7.30考试

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

1105
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

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

3245
来自专栏算法修养

整数划分总结

整数划分问题: 笼统上说就是将一根整数划分成若干个整数之和的方案数。整数划分很多不同的问法,也有隐晦的问法。比如n个苹果放到m个盘子里,比如n个砖块堆成m个...

3056
来自专栏程序员叨叨叨

7.1 Cg 关键字第 7 章 输入\输出与语义绑定

第三章从 GPU 运行原理和数据流程的角度阐述了顶点着色程序和片段着色程序的输入输出,即,应用程序(宿主程序)将图元信息(顶点位置、法向量、纹理坐标等)传递给顶...

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

Direct3D学习(四):高级着色语言初探

1337

扫码关注云+社区