您當前位置：首頁 > php開源 > php教程 > DFS（深度優(yōu)先）算法編程實踐

DFS（深度優(yōu)先）算法編程實踐

來源：程序員人生發(fā)布時間：2016-12-04 14:01:12 閱讀次數(shù)：2585次

DFS定義

DFS（Depth-First-Search）深度優(yōu)先搜索算法，是搜索算法的1種。是1種在開發(fā)爬蟲初期使用較多的方法。它的目的是要到達被搜索結(jié)構(gòu)的葉結(jié)點。

特點

每次深度優(yōu)先搜索的結(jié)果必定是圖的1個連通份量。深度優(yōu)先搜索可以從多點發(fā)起。如果將每一個節(jié)點在深度優(yōu)先搜索進程中的“結(jié)束時間”排序(具體做法是創(chuàng)建1個list,然后在每一個節(jié)點的相鄰節(jié)點都已被訪問的情況下，將該節(jié)點加入list結(jié)尾，然后逆轉(zhuǎn)全部鏈表),則我們可以得到所謂的“拓撲排序”，即topological sort.

固然,當人們剛剛掌握深度優(yōu)先搜索的時候常經(jīng)常使用它來走迷宮。事實上我們還有別的方法，那就是廣度優(yōu)先搜索 (BFS)。狀態(tài)（state)：狀態(tài)是指問題求解進程中每步的狀態(tài)。

經(jīng)典算法進程

圖的深度遍歷原則：

1 如果有可能，訪問1個領接的未訪問的節(jié)點，標記它，并把它放入棧中。

2 當不能履行規(guī)則 1 時，如果棧不為空，則從棧中彈出1個元素。

3 如果不能履行規(guī)則 1 和規(guī)則 2 時，則完成了遍歷。

典型實例（兵臨城下）

該題目是樂視的面試編程題

盧卡斯的驅(qū)逐者大軍已來到了赫柏的卡諾薩城，赫柏終究下定決心,集結(jié)了大軍,與驅(qū)逐者全面開戰(zhàn)。
盧卡斯的手下有6名天之驅(qū)逐者，這6名天之驅(qū)逐者各賦異能，是盧卡斯的主力。
為了擊敗盧卡斯，赫柏必須好好斟酌如何安排自己的狂戰(zhàn)士前去迎戰(zhàn)。
狂戰(zhàn)士的魔法與1些天之驅(qū)逐者的魔法屬性是相克的，第i名狂戰(zhàn)士的魔法可以克制的天之驅(qū)逐者的集合為Si(Si中的每一個元素屬于[0,5])。
為了公平，兩名狂戰(zhàn)士不能攻擊同1個天之驅(qū)逐者。
現(xiàn)在赫柏需要知道共有多少種分派方案。
例：
S1={01},S2={23}，代表編號為0的狂戰(zhàn)士的魔法可以克制編號為0和編號為1的天之驅(qū)逐者，編號為1的狂戰(zhàn)士的魔法可以克制編號為2和編號為3的天之驅(qū)逐者，共有4種方案：02,03,12,13。
02—代表第1個狂戰(zhàn)士負責編號為0的驅(qū)逐者，第2個狂戰(zhàn)士負責編號為2的驅(qū)逐者；
03—代表第1個狂戰(zhàn)士負責編號為0的驅(qū)逐者，第2個狂戰(zhàn)士負責編號為3的驅(qū)逐者；
12—代表第1個狂戰(zhàn)士負責編號為1的驅(qū)逐者，第2個狂戰(zhàn)士負責編號為2的驅(qū)逐者;
13—代表第1個狂戰(zhàn)士負責編號為1的驅(qū)逐者，第2個狂戰(zhàn)士負責編號為3的驅(qū)逐者;
S1={01},S2={01}，代表編號為0的狂戰(zhàn)士的魔法可以克制編號為0和編號為1的天之驅(qū)逐者，編號為1的狂戰(zhàn)士的魔法可以克制編號為0和編號為1的天之驅(qū)逐者，共有兩種方案：01,10。

輸入描寫:

多組測試數(shù)據(jù)，請?zhí)幚淼轿募Y(jié)束。

對每組測試數(shù)據(jù)：

第1行動1個整數(shù)N，代表狂戰(zhàn)士的數(shù)量。

第2行動N個字符串，第i個字符串表示第i個狂戰(zhàn)士能夠克制的天之驅(qū)逐者的集合。

保證：

1<=N<=6，1<=每一個字符串的長度<=6，且每一個字符都是0~5中的1個數(shù)字。

輸出描寫:

輸出1個整數(shù)，代表分配方案數(shù)

輸入例子:

2
01 23
2
01 01
3
3 015 5

輸出例子:

4
2
2

分析：

1.對這類遍歷的問題，斟酌采取經(jīng)典的DFS，設置1個輔助的數(shù)組（題目要求不能兩個人打1個），來記錄是不是是不是是唯1的。

2.判斷每一個分支的截止條件，通過遞歸和循環(huán)完成遍歷。

代碼：

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

}