文档章节

DFS(深度优先)算法编程实践

fengsehng
 fengsehng
发布于 2016/11/09 09:08
字数 1272
阅读 3
收藏 0

DFS定义

DFS(Depth-First-Search)深度优先搜索算法,是搜索算法的一种。是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点 。

特点

每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起。如果将每个节点在深度优先搜索过程中的“结束时间”排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的“拓扑排序”,即topological sort.

当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫。事实上我们还有别的方法,那就是广度优先搜索 (BFS)。状态(state):状态是指问题求解过程中每一步的状况。

经典算法过程

图的深度遍历原则:

1 如果有可能,访问一个领接的未访问的节点,标记它,并把它放入栈中。

2 当不能执行规则 1 时,如果栈不为空,则从栈中弹出一个元素。

3 如果不能执行规则 1 和规则 2 时,则完成了遍历。

典型实例(兵临城下)

该题目是乐视的面试编程题

卢卡斯的驱逐者大军已经来到了赫柏的卡诺萨城,赫柏终于下定决心,集结了大军,与驱逐者全面开战。
卢卡斯的手下有6名天之驱逐者,这6名天之驱逐者各赋异能,是卢卡斯的主力。
为了击败卢卡斯,赫柏必须好好考虑如何安排自己的狂战士前去迎战。
狂战士的魔法与一些天之驱逐者的魔法属性是相克的,第i名狂战士的魔法可以克制的天之驱逐者的集合为Si(Si中的每个元素属于[0,5])。
为了公平,两名狂战士不能攻击同一个天之驱逐者。
现在赫柏需要知道共有多少种分派方案。
例:
S1={01},S2={23},代表编号为0的狂战士的魔法可以克制编号为0和编号为1的天之驱逐者,编号为1的狂战士的魔法可以克制编号为2和编号为3的天之驱逐者,共有四种方案:02,03,12,13。
02—代表第一个狂战士负责编号为0的驱逐者,第二个狂战士负责编号为2的驱逐者;
03—代表第一个狂战士负责编号为0的驱逐者,第二个狂战士负责编号为3的驱逐者;
12—代表第一个狂战士负责编号为1的驱逐者,第二个狂战士负责编号为2的驱逐者;
13—代表第一个狂战士负责编号为1的驱逐者,第二个狂战士负责编号为3的驱逐者;
S1={01},S2={01},代表编号为0的狂战士的魔法可以克制编号为0和编号为1的天之驱逐者,编号为1的狂战士的魔法可以克制编号为0和编号为1的天之驱逐者,共有两种方案:01,10。

输入描述:

多组测试数据,请处理到文件结束。

对于每组测试数据:

第一行为一个整数N,代表狂战士的数量。

第二行为N个字符串,第i个字符串表示第i个狂战士能够克制的天之驱逐者的集合。

保证:

1<=N<=6,1<=每个字符串的长度<=6,且每个字符都是0~5中的一个数字。

输出描述:

输出一个整数,代表分配方案数

输入例子:

2
01 23
2
01 01
3
3 015 5

输出例子:

4
2
2

分析:

1.对于这种遍历的问题,考虑采用经典的DFS,设置一个辅助的数组(题目要求不能两个人打一个),来记录是否是否是唯一的。

2.判断每个分支的截止条件,通过递归和循环完成遍历。

代码:

public class Main {

    private static int ans;

    public static int getAns(String[] str, int n) {
        ans = 0;
        int[] vis = {0, 0, 0, 0, 0, 0};
        dfs(str, vis, n, 0);
        return ans;
    }

    public static void dfs(String[] str, int[] vis, int n, int p) {
        if (p == n) {
            ans++;
            return ;
        }
        for (int i = 0; i < str[p].length(); i++) {
            if (vis[str[p].charAt(i) - '0'] == 0) {
                vis[str[p].charAt(i) - '0'] = 1;
                dfs(str, vis, n, p + 1);
                vis[str[p].charAt(i) - '0'] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        while (in.hasNext()) {
            int n = in.nextInt();
            String[] str = new String[n];
            for (int i = 0; i < n; i++) {
                str[i] = in.next();
            }

            int ans = getAns(str, n);
            System.out.println(ans);
        }
        in.close();
    }

}

引用:
牛客网的乐视题目

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

本文转载自:http://blog.csdn.net/lpjishu/article/details/52583518

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
JavaScript 算法与数据结构 - javascript-algorithms

javascript-algorithms 包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中...

匿名
05/31
0
0
【算法研究】搜索算法-深度优先搜索

---------- 如果您觉得本文有用,可以在微博上关注我,每周我都会在微博上发布新博客发表的通知,我的微博 深度优先搜索 介绍 如果您觉得这篇文章排版不舒服,请到我的微盘下载pdf:搜索算法...

王选易
2013/12/13
0
3
JavaScript 算法与数据结构

本仓库包含了多种基于 JavaScript 的算法与数据结构。 每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。 数据结构 数据结构是在计算机中组织和存储数据的...

a独家记忆
06/08
0
0
各种基本算法实现小结(四)—— 图及其遍历

各种基本算法实现小结(四)—— 图及其遍历 (均已测试通过) ==================================================================== 图——深度优先和广度优先算法 无向图用二维邻接矩阵...

长平狐
2013/01/06
198
0
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

[MicroPython]STM32F407开发板驱动OLED液晶屏

1.实验目的 1.学习在PC机系统中扩展简单I/O 接口的方法。 2.进一步学习编制数据输出程序的设计方法。 3.学习 F407 Micropython开发板控制OLED显示字符。 2.所需元器件 F407 Micropython开发板...

bodasisiter
33分钟前
0
0
php require和include 相对路径一个有趣的坑

以前总是被教育,不要使用相对路径,这样性能比较差,但是相对路径的问题不仅仅是性能哦,看下面这里例子 这是项目结构 .├── main.php├── t│ ├── t1.php│ └── t2.php└─...

anoty
33分钟前
17
0
x64技术之SSDT_Hook

测试环境: 虚拟机: Windows 7 64bit 过PG工具 驱动加载工具 PCHunter64 系统自带的计算器和任务管理器等 实现思路: 实际思路与win32的思路一样.都是替换SSDT表里边的函数地址.不过微软被搞怕...

simpower
34分钟前
0
0
TreeMap源码分析,看了都说好

一、简介 TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作,效率很...

Java小铺
44分钟前
0
0
协变、逆变

概念 假设 A、B表示类型 ≤ 表示继承关系 f<⋅>表示类型转换 若A ≤ B,则 A是B的子类,B是A的超类 协变、逆变 什么是型变?型变(type variance)允许对类型进行子类型转换。 为了下面讲解先...

obaniu
50分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部