目錄

一.標(biāo)準(zhǔn)定義

二.跳臺(tái)階（典型遞歸題目）

三.遞歸實(shí)現(xiàn)指數(shù)型枚舉

四.遞歸實(shí)現(xiàn)排列型枚舉

五.遞歸實(shí)現(xiàn)組合型枚舉

六.DFS算法模板

一.標(biāo)準(zhǔn)定義

深度優(yōu)先搜索算法（Depth First Search，簡(jiǎn)稱DFS）：一種用于遍歷或搜索樹或圖的算法。 沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過或者在搜尋時(shí)結(jié)點(diǎn)不滿足條件，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。屬于盲目搜索,最糟糕的情況算法時(shí)間復(fù)雜度為O(!n)。

?

說人話，其實(shí)就是沿著一條路一直搜索，知道條件不符合，就回頭走到分岔口，選擇另一條路繼續(xù)搜索，俗稱：“不撞南墻不回頭”搜索。

這種一直進(jìn)行下去又返回的操作是不是很像遞歸，dfs名字聽起來高大上，其實(shí)本質(zhì)就是遞歸。那我們就先從一道典型的遞歸題開始說起吧。

二.跳臺(tái)階（典型遞歸題目）

上樓梯的同學(xué)，每次可以走一個(gè)臺(tái)階，也可以走兩個(gè)臺(tái)階，現(xiàn)在有N個(gè)臺(tái)階，請(qǐng)問有多少種不同的方法？（先爬1階再爬2階和先爬2階再爬1階是不同的方法）

我們可以自己在草稿紙上算算，看看有什么規(guī)律。

N=1，1種；

N=2，1+1/2? ?2種

N=3 1+1+1/1+2/2+1? ?3種

N=4 1+1+1+1/2+2/1+2+1/2+1+1/1+1+2? ?5種

......?

很顯然，其實(shí)你會(huì)發(fā)現(xiàn)答案成斐波那契數(shù)列（當(dāng)然，本題答案是從斐波拉契數(shù)列第二項(xiàng)開始的)。這就把題目轉(zhuǎn)換成我們熟悉的問題了。

對(duì)于斐波那契數(shù)列，我們可以引用一種”遞歸搜索樹“的方法，來讓整個(gè)過程更加直觀。?

我們先沿著左邊①這條路一直往下算，直到遇到了f(2)（因?yàn)槲覀冎纅(1),f(2)的值)，然后撞到了”南墻“，我們就開始回溯，算f(1)，兩者累加算出f(3)的值，接著回溯算f(2)的值......?

這個(gè)過程其實(shí)就體現(xiàn)了什么加”深度搜索“，什么叫”回溯“。

我們簡(jiǎn)單看一下這道題的代碼。

#include<stdio.h>
int fun1(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
		return fun1(n - 1) + fun1(n - 2);
}

什么？覺得簡(jiǎn)單？我們開始上強(qiáng)度了。?

再講下面題之前，我先給出dfs算法基本套路。

三.DFS算法模板

1.創(chuàng)建一個(gè)數(shù)組，存儲(chǔ)狀態(tài)和結(jié)果。

2.函數(shù)內(nèi)部

①判斷是否撞了南墻

②執(zhí)行賦值，改狀態(tài)的操作

③再次調(diào)用函數(shù)

④恢復(fù)現(xiàn)場(chǎng)

四.遞歸實(shí)現(xiàn)指數(shù)型枚舉

我們先看看這道題?？梢試L試運(yùn)用樹形圖的方法找找思路。

通過判斷一個(gè)數(shù)選不選的思路，我們可以畫出樹狀圖。

這是我沒畫完的樹狀圖，你看，這樣就能找到2個(gè)答案了。?

我們把圖補(bǔ)全，8個(gè)答案就已經(jīng)全部找到了。?

?接著，我們進(jìn)行代碼實(shí)現(xiàn)，注意看我的注釋>

如何讓程序知道一個(gè)數(shù)選沒選呢？那就需要使用一個(gè)狀態(tài)數(shù)組，存儲(chǔ)一個(gè)數(shù)的狀態(tài)，是選了還是沒選還是還沒考慮到。

#include <stdio.h>
int n;
int st[20] = { 0 };//記錄每個(gè)數(shù)的狀態(tài)，0代表還沒考慮，1代表選了，2代表沒選
void dfs(int x)//x表示當(dāng)前枚舉到了哪個(gè)位置
{
	//判斷是不是撞了"南墻"了
	if (x > n)
	{
		for (int i = 1; i <= n; i++)
		{
			if (st[i] == 1)
			{
				printf("%d ", i);
			}
		}
		printf("\n");
		return;
	}

	//選
	st[x] = 1;
	dfs(x + 1);
	st[x] = 0;//恢復(fù)現(xiàn)場(chǎng)（下面有解釋）

	//回溯以后，就該不選了
	st[x] = 2;
	dfs(x + 1);
	st[x] = 0;
}

int main()
{
	scanf("%d", &n);
	dfs(1);//把位置1傳過去
	return 0;
}

代碼配合樹狀圖更好理解，一定要切記，當(dāng)一條路走不通的時(shí)候才會(huì)發(fā)生回溯?。?！

為什么要恢復(fù)現(xiàn)場(chǎng)？其實(shí)就是為了恢復(fù)到上一個(gè)分岔口的狀態(tài)，把數(shù)字標(biāo)記為還沒有考慮。這個(gè)操作可以讓回溯的過程更加清晰。

看到這里，不知道你的精神狀態(tài)是怎樣的？如果你感到->

不要慌張，熟能生巧~

五.遞歸實(shí)現(xiàn)排列型枚舉

同樣的，上例題

當(dāng)n=3時(shí)，由高中學(xué)的排列組合知識(shí)，那么就有A3 3=3*2*1=6種排列方式，符合輸出結(jié)果。

我們可以根據(jù)依次枚舉一個(gè)位置上選哪個(gè)數(shù)的思路，來畫個(gè)樹狀圖，試試呢？

我們一起來看看代碼如何實(shí)現(xiàn)的

#include <stdio.h>
#include <stdbool.h>

int n = 0;
bool st[10];//因?yàn)橐粋€(gè)數(shù)只能出現(xiàn)一次，所以用一個(gè)狀態(tài)數(shù)組存一下一個(gè)數(shù)是否已經(jīng)被選。
//true表示選過，false表示未被選。
int arr[10] = { 0 };//存的是答案，例如123/321/312

//x表示枚舉到的位置
void dfs(int x)
{
	if (x>n)
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%d", arr[i]);
		}
		printf("\n");
		return;
	}
	
	for (int i = 1; i <= n; i++)
	{
		if (!st[i])//如果st[i]是false
		{
			st[i] = true;
			arr[x] = i;
			dfs(x + 1);
			//恢復(fù)現(xiàn)場(chǎng)
			st[i] = false;
			arr[x] = 0;
		}
	}
}
int main()
{
	scanf("%d", &n);
	dfs(1);
	return 0;
}

大家可以運(yùn)用編譯器的調(diào)試功能，一步步看怎么運(yùn)行的?；蛘?strong>自己口述整個(gè)過程的邏輯，來加深自己的理解。?

（對(duì)了，如果題目要ac的話，注意在輸出的時(shí)候使用%5d就能保留5個(gè)場(chǎng)寬啦~）

六.遞歸實(shí)現(xiàn)組合型枚舉

加油，最后一個(gè)類型了！

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

我們來看題。

?當(dāng)n=5，r=3時(shí)，由高中學(xué)的排列組合知識(shí)，不考慮順序，那么就有C5?3=C5 2=10種排列方式，符合輸出結(jié)果。

我們可以發(fā)現(xiàn)，每一行的數(shù)是遞增的，我們也可以通過枚舉一個(gè)位置上選什么數(shù)的思路來畫出樹狀圖，自己試試吧！

當(dāng)一條路沒有結(jié)果的時(shí)候，我們把這種舍棄它的行為稱作”剪枝“。

對(duì)于代碼的實(shí)現(xiàn)，我們運(yùn)用：

int x;記錄當(dāng)前枚舉到了哪個(gè)位置

int arr[x];記錄都選了哪些數(shù)（記答案）

int start;（記錄下個(gè)位置從幾開始枚舉）

#include <stdio.h>
int n, r;
int arr[21];

void dfs(int x,int start)
{
	if (x > r)
	{
		for (int i = 1; i <= r; i++)
		{
			printf("%3d", arr[i]);
		}
		printf("\n");
		return;
	}

	for (int i = start; i <= n; i++)
	{
		arr[x] = i;
		dfs(x + 1, i + 1);
		arr[x] = 0;//恢復(fù)
	}
}

int main()
{
	scanf("%d %d", &n, &r);
	dfs(1,1);
	return 0;
}

?恭喜，你完成了DFS算法的學(xué)習(xí)！

接下來就是刷題啦，在我的下一篇文章里，我們一起來刷題~?

已更新：C語言dfs深度優(yōu)先練習(xí) N皇后 圖文并茂超詳解 ！

? ? ? ? ? ? ??DFS練習(xí)-迷宮（最短路徑）問題詳解 一波三折 圖片+文字文章來源地址http://www.zghlxwxcb.cn/news/detail-765619.html

到了這里，關(guān)于C語言遞歸+DFS（深度優(yōu)先搜索算法）詳解 圖文并茂，手把手教你畫樹狀圖的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！