1 深度优先算法
- 深度优先搜索算法（DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
2.1 全排列问题
- 例如，将a、b、c三个字符进行排列（可以假定放在不同的箱子里）
- 首先将a放在了1号箱子中（假定每次到一个箱子都先放a，再放b，最后放c）；
- 然后，将b放在了2号箱子；将c放在了3号箱子；
- 到4号箱子时，已经没有字符了（边界条件），可以输出一个排列abc；
- 然后再取回3号箱子中的c，当想要再往3号箱子放别的字符时，发现手中只有c，没有别的选择；
- 于是再回到2号箱子，收回b，现在有了两个字符b和c。按照之前的规定，现在需要往2号箱子里放c（上一次放的是b）。放好以后向后走一步，再次来到3号箱子，将仅剩的b放入了3号箱子；
- 又一次来到4号盒子，已经没有字符了（边界条件），又可以输出一个排列acb；
- 同理，再收回1、2和3箱子中的a、b、c，将1号箱子放入b，得到bac和bca两种排列；
- 再收回1、2和3箱子中的a、b、c，将1号箱子放入c，得到cab和cba两种排列；
- 累计6种排列。在排列过程中需要知道哪些字符已经放进了箱子，即有哪些字符可以放进后面的箱子里
2.2 代码实现（以5个字符为例）
#include#define N 5 char re[N] = {0}; //每一次全排列的结果 int vi[N] = {0}; //表示对应索引下的字符是否已使用掉，0表示未使用 char str[N] = {'a', 'b', 'c', 'd', 'e'}; //可以放置的所有字符 int count = 0; //计算排列次数 void dfs(int step) { if (step == N) //累计N个字符，索引为[0,N-1],step=N时说明所有字符已经被用掉 { //遍历此次排列的字符 count++; printf("第%d次排列组合为:", count); for (int i = 0; i < N; i++) printf("%c->", re[i]); puts(""); return; } for (int i = 0; i < N; i++) //遍历所有的字符，后再用0和1判断能否使用 { if (vi[i] == 0) //暂时还未使用掉str[i] { re[step] = str[i]; // re[step]不是re[i] vi[i] = 1; //表示str[i]被用掉了 dfs(step + 1); //递归，得到re[step+1] vi[i] = 0; //回退到上一步，回收str[i] } } return; } int main() { dfs(0); return 0; }
2.3 代码结果
3.1 环排列问题
- 将N个数字就行排列，排列为一个环，要求i和i+1索引下数据之和为素数，环的末位数和首位数相邻，之和也为素数。首位数字排1。
- 思路和全排列问题基本类似，增加素数的判断即可。以10个数据为例实现代码。
3.2 代码实现
#include#include bool isPrime(size_t n); bool sumIsPrime(int step, int i); #define N 10 int re[N] = {0}; //每一次全排列的结果 int vi[N] = {0}; //表示对应索引下的数字是否已使用掉，0表示未使用 size_t nums[N] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; //可以放置的所有数字 int count = 0; //计算排列次数 bool isPrime(size_t n) //判断n是否为素数 { if (n == 0 || n == 1) // 0和1不是素数 return false; for (int i = 2; i <= n - 1; i++) { if (n % i == 0) return false; } return true; } bool sumIsPrime(int step, int i) //判断i索引下的数据nums[i]能否放在re[step] { if (!vi[i]) //即vi[0]为0，表示还未放置 { if (step == N - 1) //如果要排列最后一个数，与下一个数（nums[0]）之和为素数才可 return isPrime(nums[i] + re[0]); return isPrime(nums[i] + re[step - 1]); } return false; } void dfs(int step) { if (step == N) //累计N个数字，索引为[0,N-1],step=N时说明所有数字已经被用掉 { //遍历此次排列的数字 count++; printf("第%d次排列组合为:", count); for (int i = 0; i < N; i++) printf("%d->", re[i]); puts(""); return; } for (int i = 1; i < N; i++) //遍历所有的数字，后再用0和1判断能否使用 { if (sumIsPrime(step, i)) //和下一个相邻的数之和为素数时（sumIsPrime函数已包含是否已放置的判断） { re[step] = nums[i]; // re[step]不是re[i] vi[i] = 1; //表示nums[i]被用掉了 dfs(step + 1); //递归，得到re[step+1] vi[i] = 0; //回退到上一步，回收nums[i] } } return; } int main() { re[0] = 1;//首位数字放1 dfs(1); return 0; }
3.3 代码结果如下：
