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

DFS（深度優先）算法編程實踐

來源：程序員人生發布時間：2016-12-04 14:01:12 閱讀次數：2578次

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

}