算法基础 排序(二)

深度优先搜索

什么是深度优先搜索?

水平有限,并不能以一种通俗易懂的方式来直接说明,所以以下面的例子来说明.

题目 输出123456789的全排列

用深度优先搜索 主要是用递归的方式来进行搜索,而每次递归说明的是当前干什么

int num[10];//由于数组从0开始计数,所以我们声明一个10个长度的数组,其中第0个不使用
int book[10];//声明一个标记数组,用于标记哪些数字用过
void func(int step){//step 说明的是第几个数
    if (step > 9){//如果大于9 说明前面9个数已经放置结束,这个时候结束递归并且打印
        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;//标记使用过
            func(step+1);
            book[i] = 0;//当递归结束返回继续执行时,这个位置的数字重新赋值,所以要把之前赋值的标记删除
        }  
    }   
}
int main(){
  func(1);
}