DFS算法（C／C++）（内含立例题）

DFS：

DFS又称深度优先搜索，是一种图运算方法，它从第一个节点走起，一直往下走，一直走到不能继续再走，就返回上一个节点，继续搜索其他地方，直到找到目标节点为止。

DFS可以解决迷宫问题：

1.先选择一条路一直走下去，直到遇到死胡同，不能继续往下走时；

2.返回上一个分岔口，选择其他路径走，一定能找到一条通往出口的路

DFS更加适合处理深度优先的问题

废话不多说，直接上例题

例题

洛谷P1036 [NOIP2002 普及组] 选数

PS：这是一道纯暴力搜索的问题，前提是要会递归（!ovo!)

题目描述：

AC代码：

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int n, k;
int a[100000];
//一个简单的判断素数的函数
int is(int x) {
	if (x == 1) {
		return 0;
	}
	else if (x == 2) {
		return 1;
	}else{
		for (int i = 2; i <= sqrt(x); i++) {
			if (x % i == 0) {
				return 0;
			}
		}
		return 1;
	}
}
int num1 = 0;    //记录种类数
void dfs(int num, int sum, int kai) {
	//num是当前相加的数字个数
	//sum是num个数相加的总和
	//kai是起始的数字位置
	if (num == k) {     //当相加的数字总数等于k时
		if (is(sum) == 1) {
			num1++;        //是素数就有一个满足题意的值
		}
		return ;
	}
	else {
		for (int i = kai; i < n; i++) {        //从起始位置向后进行递归搜索
			dfs(num + 1, sum + a[i], i + 1);
		}
	}
}
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);    //这里的排序写在底下了嗷
	dfs(0, 0, 0);       //起始的num,sum,kai都是0
	cout << num1 << endl;
	return 0;
}