Java实现深度搜索DFS算法详解

2024-09-28 06:16:28

DFS概述

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

解释

思路

一般用矩阵表示，从当前点开始，依次向周围四个方向试探，在我们给定数值条件下依次搜索（1代表不能走，0代表能走），对走过的路进行标记，如果最终达到了要走的点，就会进行回溯，回溯时，会将已经走过的点再次标记为未走，回到出发点，进行别的方向的试探

当找到距离最短的，而且到达了终点时，停止访问，输出结果

案例题-单身的蒙蒙

题目描述

蒙蒙要找对象啦！但是对象在和他玩捉迷藏，现在有一个55的地图，蒙蒙就在（0，0）的位置，他的心上人就在（4，4）的位置，当然路上会有各种艰难险阻，现在说明一下规则。蒙蒙按照地图行动，一次走一步，而且他只能前后左右的移动，当然蒙蒙也不能穿越墙壁。地图上有两种图案，一种是‘0'表示可以走的路，另一种是‘1'表示不能走的墙

PS:（0，0）就是左上角，（4，4）就是右下角，都懂吧！

输入：

输入一个55的矩阵表示地图，‘0'表示可以走的路，‘1'表示不能走的墙，蒙蒙就在（0，0）的位置，他的心上人就在（4，4）的位置

输出：

输出蒙蒙到心上人那里最少要走多少步，若蒙蒙永远走不到心上人那里，则输出-1

输入样例：

0 1 0 0 0

0 0 0 1 0

0 1 0 1 0

0 1 0 0 0

0 0 0 1 0

输出样例：

题解

分析: 首先分析下，主人公要想能够找到对象，就需要走到左下角，而去的过程显然不是一帆风顺的，它会遇到墙壁，遇到墙壁就会返回，返回到前一个点之后向其他方向进行搜索，如果有通路，就会接着执行这步的操作，直到找到终点。题目中问的是最少要通过多少步才能找到对象，那么显然可能一次搜索找不到最短的路径，这里就需要回溯，把回溯的点设置为未标记，回溯到最初的点之后进行其他方向的遍历，如果第二次到达终点的值小于第一次的就更新路径，将第二次的路径作为最小的路径，直到所有点遍历完

//回溯算法
flag[xx][yy]=1//标记
dfs(1,1,step+1)
//flag[xx][yy]=0;设置为未标记的点，进行回溯

方向数组因为要进行四个方向的试探，所以要定义一个方向数组：方向数组的定义可以使用一维数组，亦可以使用二维数组，建议大家使用一维数组，直观明了，这里解释下便于方便，将标准坐标轴顺时针方向旋转了90度，令x=0;y=0则可有四个方向坐标右：（0，1），下：（1，0），左：（0，-1），上：（-1，0），依次取dx一次，dy一次，就和上面的坐标一致了

    static int[] dx = {0, 1, 0, -1};//方向数组，顺时针：右 下 左 上
    static int[] dy = {1, 0, -1, 0};

注意事项: 这里因为输入的是从原点开始，而外界临界值也是等同于墙壁，为了免去试探，可以将四边的设置为“1”墙壁，这样可以避免数组越界

 //试探墙壁，避免越界
        for(int i = 0; i <=6;i++){
           s[0][i]=1;
           s[i][0]=1;
           s[6][i]=1;
           s[i][6]=1;
        }

整体代码

import java.util.Scanner;
public class test2 {

    static int[][] s = new int[10][10];
    static int[][] flag = new int[10][10];

    static int min = 99;//初始化认为该路径很大
    static int[] dx = {0, 1, 0, -1};//方向数组，顺时针：右 下 左 上
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //试探墙壁，避免越界
        for (int i = 0; i <= 6; i++) {
            s[0][i] = 1;
            s[i][0] = 1;
            s[6][i] = 1;
            s[i][6] = 1;
        }
        //将外围墙壁左上角顶点设置为（0，0）
        for (int i = 1; i < 6; i++)//这里的从1开始，省去外围墙壁带来的不便
        {
            for (int j = 1; j < 6; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        int sx = 1, sy = 1;//从（1，1）开始
        flag[sx][sy] = 1;//进行标记
        dfs(sx, sy, 0);//搜索
        if (min == 99)//如果值还是原来的，就说明不存在
            System.out.println("-1");
        else
            System.out.println(min);
    }

    public static void dfs(int x, int y, int step) {
        if (x == 5 && y == 5) {//到达了右下角，终点
            if (step < min) {//如果当前步数小于之前的
                min = step;//标记更新
            }
            return;//否则返回空
        }
        for (int i = 0; i < 4; i++) {//控制方向数组
            int xx = x + dx[i];//进行右，下，左，上搜索
            int yy = y + dy[i];
            if (flag[xx][yy] == 0 && s[xx][yy] == 0) {//如果未被标记，并且原来该位置的值为0
                flag[xx][yy] = 1;//标记
                dfs(xx, yy, step + 1);
                flag[xx][yy] = 0;//回溯
            }
        }

    }
}

到此这篇关于Java实现深度搜索DFS算法详解的文章就介绍到这了,更多相关Java 深度搜索DFS算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

Java实现二叉树的深度优先遍历和广度优先遍历算法示例

本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然
Java编程实现基于图的深度优先搜索和广度优先搜索完整代码

为了解15puzzle问题,了解了一下深度优先搜索和广度优先搜索.先来讨论一下深度优先搜索(DFS),深度优先的目的就是优先搜索距离起始顶点最远的那些路径,而广度优先搜索则是先搜索距离起始顶点最近的那些路径.我想着深度优先搜索和回溯有什么区别呢?百度一下,说回溯是深搜的一种,区别在于回溯不保留搜索树.那么广度优先搜索(BFS)呢?它有哪些应用呢?答:最短路径,分酒问题,八数码问题等.言归正传,这里笔者用java简单实现了一下广搜和深搜.其中深搜是用图+栈实现的,广搜使用图+队列实现的,代码如下:
java图的深度优先遍历实现随机生成迷宫

最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢. 1.从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中的随机一个访问(每访问到一个可访问的点,就去掉该点的那个方向的墙),被访问点继续以这种方识向下进行访问. 2.对每个被访问的点都被标识为已访问,当一个点对某个方向进行访问时我们首先会判断被访问点是否已被访问,或者触到边界.如果该点四个方向皆已访
深度优先与广度优先Java实现代码示例

在编程生活中,我们总会遇见树性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及过程.现在假设有一颗这样树,(是不是二叉树都没关系,原理都是一样的) 1.深度优先英文缩写为DFS即Depth First Search. 深度优先搜索是一种在开发爬虫早期使用较多的方法.它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) .在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链.深度
java图搜索算法之DFS与BFS详解

目录一.前言二.深度优先搜索三.广度优先搜索四.结语你好,我是小黄,一名独角兽企业的Java开发工程师. 感谢茫茫人海中我们能够相遇, 俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习, 希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想. 一.前言上一篇文章我们提到了关于图的形象化描述方法,不知道大家还有没有印象.没有印象的话,可以去看一下上期的内容对于图来说,搜索的方法无外乎两种,深度优先搜索(DFS)和广度优先搜索(BFS) 两种搜索算法也不太相同,
Java实现深度搜索DFS算法详解

目录 DFS概述解释思路案例题-单身的蒙蒙题目描述题解整体代码 DFS概述深度优先搜索是一种在开发爬虫早期使用较多的方法.它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) .在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链.深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链.当不再有其他超链可选择时,
Java垃圾回收之复制算法详解

之前的Java垃圾回收之标记清除算法详解会导致内存碎片.下文的介绍的coping算法可以解决内存碎片问题. 概述如果jvm使用了coping算法,一开始就会将可用内存分为两块,from域和to域, 每次只是使用from域,to域则空闲着.当from域内存不够了,开始执行GC操作,这个时候,会把from域存活的对象拷贝到to域,然后直接把from域进行内存清理. 应用场景 coping算法一般是使用在新生代中,因为新生代中的对象一般都是朝生夕死的,存活对象的数量并不多,这样使用coping算法
Java图论进阶之最小生成树算法详解

目录 1. 最小生成树 1.1 Kruskal(克鲁斯卡尔) 算法 1.2 Prime(普里姆) 算法总结 1. 最小生成树连通图中的每一棵生成树 , 都是原图的极大无环子图 , 即: 从中删去任何一条边 , 生成树就不再连通;反之 , 在其中引入任何一条新边 , 都会形成一条回路. 若连通图由n个顶点组成 , 则其生成树必含n个顶点和n-1条边 , 因此构造最小生成树有三个准则: 1.只能使用图中的边来构造最小生成树 2.只能使用恰好n-1条边来连接图中的n个顶点 3.选用的n-1条边不能
Java实现的最大匹配分词算法详解

本文实例讲述了Java实现的最大匹配分词算法.分享给大家供大家参考,具体如下: 全文检索有两个重要的过程: 1分词 2倒排索引我们先看分词算法目前对中文分词有两个方向,其中一个是利用概率的思想对文章分词. 也就是如果两个字,一起出现的频率很高的话,我们可以假设这两个字是一个词.这里可以用一个公式衡量:M(A,B)=P(AB)/P(A)P(B),其中 A表示一个字,B表示一个字,P(AB)表示AB相邻出现的概率,P(A)表示A在这篇文章中的频度,P(B)表示B在这篇文章中的频度.用概率分词的好
基于序列化存取实现java对象深度克隆的方法详解

我们知道,在java中,将一个非原型类型类型的对象引用,赋值给另一个对象的引用之后,这两个引用就指向了同一个对象,如: 复制代码代码如下: public class DeepCloneTest { private class CloneTest { private Long myLong = new Long(1); } public static void main(String args[]) { new DeepCloneTest().Test(); } public void Te
Java垃圾回收之分代收集算法详解

概述这种算法,根据对象的存活周期的不同将内存划分成几块,新生代和老年代,这样就可以根据各个年代的特点采用最适当的收集算法.可以用抓重点的思路来理解这个算法. 新生代对象朝生夕死,对象数量多,只要重点扫描这个区域,那么就可以大大提高垃圾收集的效率.另外老年代对象存储久,无需经常扫描老年代,避免扫描导致的开销. 新生代在新生代,每次垃圾收集器都发现有大批对象死去,只有少量存活,采用复制算法,只需要付出少量存活对象的复制成本就可以完成收集:可以参看我之前写的Java垃圾回收之复制算法详解老年代
Java搜索与图论之DFS和BFS算法详解

目录 DFS和BFS简介 DFS数字排序 DFS皇后排序 DFS树的重心 BFS走迷宫 BFS八数码 BFS图层次本次我们介绍搜索与图论篇中DFS和BFS,我们会从下面几个角度来介绍: DFS和BFS简介 DFS数字排序 DFS皇后排序 DFS树的重心 BFS走迷宫 BFS八数码 BFS图层次 DFS和BFS简介首先我们先来介绍一下DFS和BFS: DFS:深度优先遍历算法,我们在进行算法运算时,优先将该路径的当前路径执行完毕,执行完毕或失败后向上回溯尝试其他途径 BFS:广度优先遍历算法,
Java利用深度搜索解决数独游戏详解

目录一.问题描述二.输入和输出三.输入和输出样例四.分析五.算法设计六.代码七.测试一.问题描述数独是一项非常简单的任务.如下图所示,一张 9 行 9 列的表被分成 9 个 3*3 的小方格.在一些单元格中写上十进制数字 1~9,其他单元格为空.目标是用 1 ~9 的数字填充空单元格,每个单元格一个数字,这样在每行.每列和每个被标记为 3*3 的子正方形内,所有 1~9 的数字都会出现.编写一个程序来解决给定的数独任务. 二.输入和输出 1.输入对于每个测试用例,后面都跟 9
Java求最小生成树的两种算法详解

目录 1 最小生成树的概述 2 普里姆算法(Prim) 2.1 原理 2.2 案例分析 3 克鲁斯卡尔算法(Kruskal) 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 6 总结介绍了图的最小生成树的概念,然后介绍了求最小生成树的两种算法:Prim算法和Kruskal算法的原理,最后提供了基于邻接矩阵和邻接链表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最小生成树的
Java实现全排列的三种算法详解

目录算法一算法二算法三算法一基于递归与回溯实现.在排列1,2,3的时候,先由3向上回溯到2发现没有其他可能的情况,再回溯到1,排列为1,3,2再向上回溯到存在其他情况时,即根节点然后再排列以2为第一位的情况,重复上述过程将所有可能结果全部放入res中. 代码: import java.util.ArrayList; import java.util.List; public class h618_1 { static List<List<Integer>> res = n

Java实现深度搜索DFS算法详解

目录

DFS概述

解释

思路

案例题-单身的蒙蒙

题目描述

题解

整体代码

相关推荐

随机推荐