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

學無先后，達者為師

網站首頁 編程語言 正文

C++回溯算法之深度優先搜索詳細介紹_C 語言

作者：子夜的星 ? 更新時間： 2023-03-02 編程語言

一、前言

本文介紹了經典搜索算法： 深度優先搜索（DFS）

兩個小故事：

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

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

二、基本概念

1.簡單介紹

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

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

2.官方概念

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

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

三、動圖分析

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

動圖：

四、模板框架

以下模板來自于大佬Carl：

void DFS(參數){
    if (終止條件){
        做要做的事
        return ;//退出 
    }
    for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）)
    	{
    		處理節點;
            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數組為我們動態申請，若直接將其地址放入二維數組，path數組中的值會隨著我們回溯而逐漸變化
        //因此創建新的數組存儲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;
}

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

欄目分類
最近更新