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

相关文章

来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2818
来自专栏祝威廉

Spark Streaming Dynamic Resource Allocation

DRA has already been implemented since Spark 1.2 . However the existing Spark DR...

1393
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5866
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

1742
来自专栏码匠的流水账

聊聊FilterSecurityInterceptor

本文就来研究一下spring security的FilterSecurityInterceptor

481
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

761
来自专栏everhad

消息处理管道

TODO: 待写 消息处理管道 一个App看作是系统,外部输入消息需要经过一系列处理,涉及不同接收者。消息处理的跟踪(Trace)和结果的保存。 比如设计一个...

1936
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1152
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112

扫码关注云+社区