目錄

題目一：組隊（回溯法）

介紹：

題目：

?代碼（C++遞歸）

卡點①

卡點②?

題目二：迷宮

題目三：走方格?

這篇文章主要目的是借各種題目🍌學習深度優先搜索🍌（depth-first search）

😄純新手0.o😊

題目一：組隊（回溯法）

介紹：

👹👹深度優先搜索：

簡稱深搜或者👍爆搜（沒有什么是暴力解決不了的）

目的是遍歷，是無序的。過程是：

1、訪問頂點v
2、依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中所有和v有路徑相通的頂點被訪問💪
3、若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止

看圖：

?路徑：

a? b? d? h? d? b? e? i? e? j? e? b? a? c? f? k? f? c? g（橙色表示初次經過）

過程描述：

第一條路訪問了a,b,d,h，走到底了，就從h退回d，發現節點d沒有除h以外的沒訪問過的，就退回b，b有除d以外未訪問過的e，所以又從e開始進行dfs...

被訪問的順序：

a --> b --> d --> h --> e --> i --> j --> c --> f --> k --> g

當然初始是隨機的，它可以先從a到c，也可以先從a到b?

dfs一般找不到最優解，所以它適合給了初始條件，尋找解但不要求找最優解的題目

👹👹回溯法：

目的是求解過程，是有序的。回溯算法 =?樹的深度優先搜索 + 剪枝函數，是dfs的一種改進

一般用遞歸實現

題目：

2019藍橋杯C/C++B組ヽ(?ﾟ▽ﾟ)ノ

作為籃球隊教練，你需要從以下名單中選出 1 號位至 5 號位各一名球員，
組成球隊的5人首發陣容。
每位球員擔任 1 號位至 5 號位時的評分如下表所示。請你計算首發陣容 1
號位至 5 號位的評分之和最大可能是多少？

?代碼（C++遞歸）

#include<iostream> #include<algorithm>//max() using namespace std;int a[20][6] = //聲明初始化二維數組存儲表格數據 {{1,97,90,0,0,0},{2,92,85,96,0,0},{3,0,0,0,0,93},{4,0,0,0,80,86},{5,89,83,97,0,0},{6,82,86,0,0,0},{7,0,0,0,87,90},{8,0,97,96,0,0},{9,0,0,89,0,0},{10,95,99,0,0,0},{11,0,0,96,97,0},{12,0,0,0,93,98},{13,94,91,0,0,0},{14,0,83,87,0,0},{15,0,0,98,97,98},{16,0,0,0,93,86},{17,98,83,99,98,81},{18,93,87,92,96,98},{19,0,0,0,89,92},{20,0,99,96,95,81} };//因為是聲明二維數組，最后這里要加上";" int visit[20];//記錄20個隊員中誰被訪問過 int max_score = 0;//聲明全局變量max_score保存dfs函數里的最大值//index表示當前位置, sum是當前組合總分 void dfs(int index, int sum) {if(index == 6)//已經選完5個人，可以比較總分了{max_score = max(max_score, sum);//第一次敲我漏了這個return;}for(int i = 0; i < 20; i++)//遍歷20個隊員{if(!visit[i])//如果他沒被訪問{visit[i] = 1;//已被訪問dfs(index+1, sum+a[i][index]);//在函數參數實現了累加visit[i] = 0;//繼續嘗試下一種5人組合}} }int main() {dfs(1,0);cout<<max_score<<endl;return 0; }

輸出:? 490?

卡點①

代碼39~45行，for循環的遍歷中，dfs的遞歸，開始有點懵😫

so, 草稿紙上列出index, sum, i在第一種情況的大小?

index	? ? ? ? sum	?i
1	? ? ? ?a[0][1]	0
2	a[0][1]+a[1][2]	1
3	? ... + a[2][3]	2
4	? ... + a[3][4]	3
5	? ... + a[4][5]	4

index = 5時，就完成了5個隊員分數的相加

卡點②?

代碼37行，if(index == 6)后的return;

不清楚index到了6后，是如何返回原來的值的

下面看解析：

先分析遞歸函數中的return ，看代碼👇👇

#include<iostream> using namespace std;int Sum(int n) {cout<<n<<" ";//讓大家看下遞歸累加順序if (n <= 1)//終止條件, 且Sum(1) == 1return n;return n+Sum(n - 1);//遞歸累加 }int main() {int n;while(cin>>n){int a = Sum(n);//累加和cout<<endl<<a<<endl;cout<<endl;} }

輸入輸出

5 5 4 3 2 1 1510 10 9 8 7 6 5 4 3 2 1 5520 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 210

分析
1，C++ 遞歸函數中的return是指：
從被調用函數返回到主調函數中繼續執行，并非一遇到return整個遞歸結束

2，return 語句，顧名思義是終止當前正在執行的函數并將控制權返回到調用該函數的地方

3，在void的函數中也可以多次使用return，功能和循環中的break一樣，在中間位置提前退出正在執行函數，也就是回到原來位置執行下一行代碼

4，return; 表示結束本次函數

5，?遞歸中的return常用來作為遞歸終止的條件，當達到遞歸終止條件時，首先return的是最底層調用的函數，return之后，繼續執行上一層調用該函數之后的代碼?

在我對return進行理解時，這篇文章給了我一定啟發關于遞歸中return的理解（最淺顯易懂）_Pledgee的博客-CSDN博客_遞歸函數return怎么理解

🔒首先1,2,3,4分別占據1,2,3,4位置，5號位置就可以依次讓隊員5-20占據；然后4號位給5號隊員，又是一種新的情況，5號位可以依次給6-20號位占據；依次這樣搜索，每個人都可以換個位置。
??其實就是一個排列組合問題，在20個人中選擇五個人，依次排列??

🔒所以說，index到了6后，返回原來遞歸位置的下一步，return到index=5，然后五號位 通過i ++，由5號隊員占據，到6號占據，一直到20號，接著return到四號位index=4，i++使5號隊員占據4號位，index+1，index = 5，五號位 i 又由6到20占據... ...

看圖

題目二：迷宮

基礎概念：

1，棧中的“先進后出，后進先出”什么意思

棧類似于彈匣，就像裝子彈壓彈進彈匣一樣，一粒一粒壓進去，但是退子彈是從最上面開始的，最先壓進去的最后彈出來，最后一個壓進去的第一個彈出來，這就是“先進后出”，也叫“后進先出”

2，棧的定義

?棧就是數據暫時存儲的地方，所以才有進棧，出棧的說法

3，棧與隊列的區別

棧是把子彈子彈壓進彈匣，后進的先出；隊列就像排隊，你第一個排，那就第一個輪到你，這就是先進先出，也叫后進后出。dfs（深度優先搜索）應用棧，而bfs（廣度優先搜索）應用隊列。棧占用空間小，而堆中的bfs常用于最短路。

4，棧在計算機領域的解釋

棧作為一種數據結構，是只能在一端進行插入和刪除的特殊線性表，它按照后進先出的原則存儲數據，先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始讀。允許進行插入和刪除操作的一段稱為棧頂(top)，另一端稱為棧底(bottom)。棧底固定，而棧頂浮動；棧中元素個數為0時成為空棧。插入數據稱為進棧(PUSH)，刪除數據稱為退棧(POP)，棧也稱后進先出表。棧在函數調用時可以可以存儲斷點，做遞歸時要用到棧！

5，堆和棧的區別

棧快捷但自由度小，堆過程長但自由度大

6，內存分配

一個由C/C++編譯的程序占用的內存分為以下幾部分：

（1）棧區(stack)--由編譯器自動分配釋放，存放函數參數值，局部變量的值等。操作方式類似于數據結構中的棧

（2）堆區(heap)--由程序員分配釋放，若程序員不釋放，程序結束時可能由OS回收。它與數據結構中的堆是兩回事，分配方式類似鏈表

（3）全局（靜態）區(static)--初始化的全局變量和靜態變量在一塊區域，未初始化的在相鄰的另一塊區域。

（4）文字常量區--常量字符串放在這里

（5）程序代碼區--存放函數體的二進制代碼

7，關于dfs，只要遞歸理解了，相關語法學習（這個我還沒學）并練習過，也就差不多了

還涉及到：malloc函數，stack(棧基本數據結構)，pop()函數，結構體還有相關頭文件等，害，沒時間搞了，我先把C++基礎語法學完再回來

最后奉上幾張圖

?

?

?第二第三張圖片來源于以下博客

迷宮算法（DFS）_熱愛編程的大忽悠的博客-CSDN博客_迷宮算法

以下是我在學習dfs過程中看的博客，就差在了語法不懂，先去MOOC學習吧：

1，最短路徑問題（更新）_skycrygg的博客-CSDN博客_最短路徑問題

2，c++深度優先搜索詳解_練習時長六年半的Programmer的博客-CSDN博客_c++深度優先搜索

3，回溯法與深度優先搜索（DFS）_lonely喆的博客-CSDN博客_回溯法和深度優先算法區別

4，深度優先搜索(DFS) 總結(算法+剪枝+優化總結)_HeartFireY的博客-CSDN博客

5，迷宮算法（DFS）_熱愛編程的大忽悠的博客-CSDN博客_迷宮算法

6，BFS和DFS_shiki11111的博客-CSDN博客_dfs和bfs

題目三：走方格?

題目

給定一個m*n方格陣，沿著方格邊線走，從左上角(0, 0)開始，每次只能往右或往下走一個單位距離，問走到右下角（m, n）一共有多少種不同走法

輸入

一行包含兩個整數 m 和 n (m >= 1 && m <= 10) && (n >= 1 && n <= 10)

輸出

輸出一個整數，表示走法數量

代碼

#include<iostream> using namespace std;int m, n, num = 0;int dfs(int x, int y) {if(x == m && y == n)num++;//走法數量+1else{if(x < m)dfs(x + 1, y);//遞歸行加一if(y < n)dfs(x, y + 1);//遞歸列加一} }int main() {while(cin>>m>>n){dfs(0, 0);cout<<num<<endl;num = 0;}return 0; }

輸入輸出

1 1 2 1 2 3 2 2 6 2 3 10 3 3 20 10 10 184756

分析?

1，首先我們明確，只能向右或下走，然后看圖

圖上粗線表示第一次路徑，代碼的關鍵在于第13行和第15行對dfs的遞歸，這也是深度優先搜索的精髓

當第一次滿足x == 2 && y == 3后，此時已到達(2, 3)，函數會return回上一步，也就是(2, 2)，但是下一步的路之前走過了，所以又返回到(2, 1)，以此類推一直return到(1, 0)，

開始第二條路徑: (1, 0) --> (1, 1) --> (1, 2) --> (1, 3) --> (2, 3)...然后繼續重復上述步驟

關于遞歸的理解其實沒什么好方法，首先你得知道你敲出dps(x + 1, y)類似代碼會出現什么樣的結果，多做點考察dfs的題，自然就懂了

總結

以上是生活随笔為你收集整理的蓝桥杯C++深度优先搜索(dfs)之组队，迷宫，走方格的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。