深度优先搜索的原理是沿着一条布满结点的路径进行搜索
如果到达一条路径的末端,
则返回上一个结点,
如果上一个结点有通往其它没有到达过的下结点,就到达此下结点
如果没有,则继续返回上一结点


利用深度优先搜索输出全排序

1
#include<stdio.h>

定义两个数组,一个变量
数组a用来存放一个数字序列
数组book用来标记已经被使用了的数字
n表示位数;
比如n=3,则输出1,2,3组成的全排序


1
int a[10],book[10],n;//c语言的全局变量在没有赋值的情况下默认为0

定义一个变量step用来表示位置,a[step]表示占据第step位的数字
因为每次判断的标准都是相同的,
都是先判断是否所有位置都放有数字了
如果没有
则用一个循环按顺序来放置一个数在当前位置
因此我们定义一个函数dfs(int step)来封装这个过程
并在函数内部使用递归的方法dfs(step+1)来实现
可以用下面一段话来概述整个过程:
循环嵌套循环加判断,
每到达第九层循环输出一个全排列,
然后依次回到上层没有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void dfs(int step)
{
int i;
if(step==n+1)//表示前n个位置都有数字占据了
{
//输出一种排序
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("\n");
return;//返回之前的一步
}
for(i=1;i<=n;i++)
{
if(book[i]==0)//book[i]等于0表示数字i还没有被使用
{
a[step]=i;
book[i]=1;//第数字i已经被使用
//到下一个位置
dfs(step+1);
//完成一次全排列后要回收部分数字(从该全排序的后往前),以用于形成新的全排序
book[i]=0;
}
}
return;
}

1
2
3
4
5
6
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}

最后更新: 2018年01月23日 10:02

原始链接: http://drac0nids.top/2017/08/28/深度优先搜索/

× 请我吃糖~
打赏二维码