深度優(yōu)先搜索

什么是深度優(yōu)先搜索?

水平有限,并不能以一種通俗易懂的方式來(lái)直接說(shuō)明,所以以下面的例子來(lái)說(shuō)明.

題目 輸出123456789的全排列

用深度優(yōu)先搜索 主要是用遞歸的方式來(lái)進(jìn)行搜索,而每次遞歸說(shuō)明的是當(dāng)前干什么

int num[10];//由于數(shù)組從0開(kāi)始計(jì)數(shù),所以我們聲明一個(gè)10個(gè)長(zhǎng)度的數(shù)組,其中第0個(gè)不使用
int book[10];//聲明一個(gè)標(biāo)記數(shù)組,用于標(biāo)記哪些數(shù)字用過(guò)
void func(int step){//step 說(shuō)明的是第幾個(gè)數(shù)
    if (step > 9){//如果大于9 說(shuō)明前面9個(gè)數(shù)已經(jīng)放置結(jié)束,這個(gè)時(shí)候結(jié)束遞歸并且打印
        for (int i = 1; i < 10; i++) {
            printf("%d",num[i]);
        }
        printf("\n");
        return;//
    }
    for (int i = 1; i < 10; i++) {
        if (book[i]==0) {
            num[step] = i;
            book[i] = 1;//標(biāo)記使用過(guò)
            func(step+1);
            book[i] = 0;//當(dāng)遞歸結(jié)束返回繼續(xù)執(zhí)行時(shí),這個(gè)位置的數(shù)字重新賦值,所以要把之前賦值的標(biāo)記刪除
        }  
    }   
}
int main(){
  func(1);
}