一、前言

本文介紹了經典搜索算法： 深度優(yōu)先搜索（DFS）

兩個小故事：

岳云鵬的相聲：孫越的爸爸帶他參觀家里面的聚寶盆，走到了一個密室門前，密室的門上上了一把鎖，孫越的爸爸身上帶了一萬多把鑰匙，他還忘了哪一把鑰匙能打開個門了，于是就一把把試，試到了最后一把，門開了。

你叫DFS，在一次校園活動中你認識了三個非常漂亮的女孩，你想和她們進一步發(fā)展。于是，你選擇了其中一個人，并對她展開了追求，你采用了 聊天->約會->表白 的戀愛三部曲。但是很不幸，她拒絕了你，于是你添加了第二個女生的微信，同樣采取了你常用的三部曲。很不幸，第二個女生也拒絕你了。但是，你沒有被困難打倒，于是你添加了第三個女生的微信，依舊是這三部曲，終于，第三個女生答應了你。你的朋友詢問你，是如何找到女朋友的？，你答：我采用了DFS對象法

二、基本概念

1.簡單介紹

前言中的兩個小故事，孫越的爸爸找鑰匙開門的過程和DFS小朋友找女朋友都是一個搜索過程。

簡而言之，搜索就是嘗試問題中所有的可能性，在所有的可能性中找到正確的結果。而深度優(yōu)先搜索用一句話概括就是：“ 一直往下走，走到最后還是走不通，那就換條路再走，直到無路可走。”用一個成語來形容，那就是 ：“ 不撞南墻不回頭。”

2.官方概念

以下是維基百科上的解釋：

深度優(yōu)先搜索算法（英語：Depth-First-Search，DFS）是一種用于遍歷或搜索樹或圖的算法。這個算法會盡可能深地搜索樹的分支。當節(jié)點v的所在邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可達的所有節(jié)點為止。如果還存在未被發(fā)現(xiàn)的節(jié)點，則選擇其中一個作為源節(jié)點并重復以上過程，整個進程反復進行直到所有節(jié)點都被訪問為止。這種算法不會根據圖的結構等信息調整執(zhí)行策略

三、動圖分析

DFS會從初始節(jié)點出發(fā)，按預定的順序擴展到下一個節(jié)點，然后從下一節(jié)點出發(fā)繼續(xù)擴展新的節(jié)點，不斷遞歸執(zhí)行這個過程，直到某個節(jié)點不能再擴展下一個節(jié)點為止。此時，則返回上一個節(jié)點重新尋找一個新的擴展節(jié)點。如此搜索下去，直到找到目標節(jié)點，或者搜索完所有節(jié)點為止。

動圖：

四、模板框架

以下模板來自于大佬Carl：

void DFS(參數){
    if (終止條件){
        做要做的事
        return ;//退出 
    }
    for (選擇：本層集合中元素（樹中節(jié)點孩子的數量就是集合的大?。?
    	{
    		處理節(jié)點;
            DFS(路徑，選擇列表);
            回溯：回到沒用過
        }
    return ;//退出 
}

五、例題分析

組合問題

題干描述

力扣77題：組合

給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。

你可以按 任何順序 返回答案。

輸入：n = 4, k = 2

輸出：

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

輸入：n = 1, k = 1

輸出：

[[1]]

思路分析

C語言代碼：

int* path;
int pathTop;
int** ans;
int ansTop;
void DFS(int n, int k,int startIndex) {
    //當path中元素個數為k個時，我們需要將path數組放入ans二維數組中
    if(pathTop == k) {
        //path數組為我們動態(tài)申請，若直接將其地址放入二維數組，path數組中的值會隨著我們回溯而逐漸變化
        //因此創(chuàng)建新的數組存儲path中的值
        int* temp = (int*)malloc(sizeof(int) * k);
        int i;
        for(i = 0; i < k; i++) {
            temp[i] = path[i];
        }
        ans[ansTop++] = temp;
        return ;
    }
    int j;
    for(j = startIndex; j <=n ;j++) {
        //將當前結點放入path數組
        path[pathTop++] = j;
        //進行遞歸
        DFS(n, k, j + 1);
        //進行回溯，將數組最上層結點彈出
        pathTop--;
    }
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    //path數組存儲符合條件的結果
    path = (int*)malloc(sizeof(int) * k);
    //ans二維數組存儲符合條件的結果數組的集合。（數組足夠大，避免極端情況）
    ans = (int**)malloc(sizeof(int*) * 10000);
    pathTop = ansTop = 0;
    DFS(n, k, 1);
    //最后的返回大小為ans數組大小
    *returnSize = ansTop;
    //returnColumnSizes數組存儲ans二維數組對應下標中一維數組的長度（都為k）
    *returnColumnSizes = (int*)malloc(sizeof(int) *(*returnSize));
    int i;
    for(i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = k;
    }
    //返回ans二維數組
    return ans;
}

到此這篇關于C++回溯算法之深度優(yōu)先搜索詳細介紹的文章就介紹到這了,更多相關C++深度優(yōu)先搜索內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論