深度优先搜索
什么是深度优先搜索?
水平有限,并不能以一种通俗易懂的方式来直接说明,所以以下面的例子来说明.
题目 输出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);
}
