一、前言

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

兩個小故事：

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

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

二、基本概念

1.簡單介紹

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

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

2.官方概念

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

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

三、動圖分析

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

動圖：

四、模板框架

以下模板來自于大佬Carl：

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

五、例題分析

組合問題

題干描述

力扣77題：組合

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

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

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

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

最新評論