您当前位置：首页 > php开源 > php教程 > DFS（深度优先）算法编程实践

DFS（深度优先）算法编程实践

来源：程序员人生发布时间：2016-12-04 14:01:12 阅读次数：2317次

DFS定义

DFS（Depth-First-Search）深度优先搜索算法，是搜索算法的1种。是1种在开发爬虫初期使用较多的方法。它的目的是要到达被搜索结构的叶结点。

特点

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

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

经典算法进程

图的深度遍历原则：

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

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

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

典型实例（兵临城下）

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

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

输入描写:

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

对每组测试数据：

第1行动1个整数N，代表狂战士的数量。

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

保证：

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

输出描写:

输出1个整数，代表分配方案数

输入例子:

2
01 23
2
01 01
3
3 015 5

输出例子:

4
2
2

分析：

1.对这类遍历的问题，斟酌采取经典的DFS，设置1个辅助的数组（题目要求不能两个人打1个），来记录是不是是不是是唯1的。

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();
    }

}