深度優(yōu)先遍歷圖的方法是，從圖中某頂點(diǎn)v出發(fā)：
- 訪問頂點(diǎn)v；
- 依次從v的未被訪問的鄰接點(diǎn)出發(fā)愚战，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點(diǎn)都被訪問齐遵；
- 若此時(shí)圖中尚有頂點(diǎn)未被訪問凤巨，則從一個(gè)未被訪問的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷洛搀，直到圖中所有頂點(diǎn)均被訪問過為止
理解深度優(yōu)先搜索的關(guān)鍵在于解決“當(dāng)下該如何做”敢茁。至于“下一步如何做”，則與“當(dāng)下該如何做”事一樣的留美。下面代碼就是深度優(yōu)先搜索的基本模型彰檬。
void dfs(int step)
{
//判斷邊界
//嘗試每一種可能
for(int i = 1; i <= n; i++){
//繼續(xù)下一步
dfs(step+1);
}
}
下面我們來看一道奧數(shù)題伸刃，口口口+口口口=口口口，將數(shù)字1~9分別填入9個(gè)口中逢倍，每個(gè)數(shù)字只能使用一次使得等式成立捧颅。例如173+286=459就是一個(gè)合理的組合，請(qǐng)問一個(gè)有多少種合理的組合呢较雕？
我們嘗試一下用深度優(yōu)先搜索來解一下這道題碉哑，19個(gè)數(shù)字，我們就把它看成是19的九張撲克牌亮蒋，然后將這九張撲克牌放到九個(gè)盒子中扣典，使得等式成立。我們用a[9]來表示盒子里面的撲克牌慎玖，那么只要判斷一下 a[1]100+a[2]10+a[3]+a[4]100+a[5]10+a[6] = a[7]100+a[8]10+a[9]這個(gè)等式是否成立贮尖。
代碼和解釋如下：
#include <stdio.h>
int a[10], mark[10], total = 0;
// step表示現(xiàn)在站在第幾個(gè)盒子面前
void depthFirstSearch(int step)
{
int i;
// 如果站在第10盒子面前，則表示前9個(gè)盒子已經(jīng)放好撲克牌
if (step == 10) {
// 判斷是否滿足等式
if (a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6] == a[7]*100+a[8]*10+a[9]) {
// 如果滿足要求可行性的解+1趁怔，并打印這個(gè)解
total++;
printf("可行性的解%d: %d%d%d + %d%d%d = %d%d%d\n",total,a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
// 返回最近調(diào)用函數(shù)的地方
return;
}
// 此時(shí)站在第step個(gè)盒子前湿硝，應(yīng)該放那張牌，按照1润努、2关斜、3...n嘗試
for (i = 1; i <=9; i++) {
// 判斷撲克牌i是否還沒有用
if (mark[i] ==0) {
a[step] = i; // 將i放到第step個(gè)盒子中
mark[i] = 1; // 將mark[i]的值設(shè)為1，表示撲克牌i已經(jīng)被用過了
// 接下來是利用遞歸放置下一個(gè)盒子的牌了
depthFirstSearch(step+1);
// 將剛才嘗試的撲克牌收回铺浇，才能進(jìn)行下一次的嘗試
mark[i] = 0;
}
}
return;
}
int main(int argc, const char * argv[]) {
depthFirstSearch(1);
// 因?yàn)?173+286 = 459 和 286+173 = 459是同一個(gè)組合
printf("有%d組",total / 2);
getchar();getchar();
return 0;
}
