欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言深度优先搜索

程序员文章站 2022-05-22 21:00:09
...

深度优先搜索:

搜索分为两类:深度优先搜索(DFS)和广度优先搜索(BFS),来看看深度优先搜索。
深度优先搜索(DFS)可以说就是“一条路走到黑”的一种搜索方法,有序的尝试每一种可能,在进行每一种可能尝试时,都将这种可能性贯彻到底,一直到该种可能被尝试到出了确切的结果或者走到了边界。深度优先搜索就是“一条路走到黑”或者“不撞南墙不回头”的搜索算法。

例子:

输入一个数n(n是不超过9的自然数),对1~n的数进行全排列后输出,每个数不能相同。这题能直接用循环解,进行枚举遍历,若数不相同就输出,现在用深度优先搜索遍历,先上代码:

#include<stdio.h>
int a[10], book[10], n;

void dfs(int step)
{
 int i;
 if(step == n + 1)        //输出条件 
 {
  for(i = 1; i <= n; i++)
  {
   printf("%d", a[i]);
  }
  printf("\n");
  return;
 }
  for(i = 1; i <= n; i++)
 {
  if(book[i] == 0)
  {
   a[step] = i;
   book[i] = 1;
   dfs(step + 1);
   book[i] = 0;
  }
 }
 return; 
}

int main()
{
 scanf("%d", &n);
 dfs(1);
 return 0;
}

对代码进行解释:

1.首先我们定义一个长度为10的数组a来储存数字,再定义一个标记数组book来标记哪些数出现过。
2.深度优先搜索代码使用递归来实现,因为每一步的处理都一样。
3.首先用一个for循环来判断哪些数没有出现过,再将这个数放入数组a的对应位置中,用book来标记此数已经出现过,递归进行下一步。
4.将刚才出现过的数重新置0,代表这个数又可以用了,再return返回上一次尝试,此时手中多了一个数,可以开始新的尝试了。

参考书:《啊哈算法》