日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁(yè) 編程語(yǔ)言 正文

C++回溯算法之深度優(yōu)先搜索詳細(xì)介紹_C 語(yǔ)言

作者：子夜的星 ? 更新時(shí)間： 2023-03-02 編程語(yǔ)言

一、前言

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

兩個(gè)小故事：

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

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

二、基本概念

1.簡(jiǎn)單介紹

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

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

2.官方概念

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

深度優(yōu)先搜索算法（英語(yǔ)：Depth-First-Search，DFS）是一種用于遍歷或搜索樹或圖的算法。這個(gè)算法會(huì)盡可能深地搜索樹的分支。當(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)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。這種算法不會(huì)根據(jù)圖的結(jié)構(gòu)等信息調(diào)整執(zhí)行策略

三、動(dòng)圖分析

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

動(dòng)圖：

四、模板框架

以下模板來自于大佬Carl：

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

五、例題分析

組合問題

題干描述

力扣77題：組合

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

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

輸入：n = 4, k = 2

輸出：

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

輸入：n = 1, k = 1

輸出：

[[1]]

思路分析

C語(yǔ)言代碼：

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

原文鏈接：https://blog.csdn.net/weixin_61084441/article/details/128652967

欄目分類
最近更新