一个深度优先搜索的小实例——数的全排列

        深度优先搜索是一个利用递归来实现的搜索算法，它是数据结构中在“树”的遍历中常用的一个很有用的算法。

        下面的一个小实例实现了输入一个0到9的数n，输出这个数的从1-n的所有全排序结果。它体现了深度优先搜索的设计思想和实现方法。

         好了，下面附上C语言实现的代码：

 

#include "stdio.h"
/**
 * 深度优先搜索：
 *     输入一个数字n， 全排列1-n: 模拟小盒子
 */
 int n;
 int book[101], a[101];

void dfs(int step)
{
    int i;
    if(step == n+1)
    {
        for(i=1; i<=n; i++)
        {
            printf("%d", a[i]);
        }
        printf("  ");
        return; //返回上一层递归
                  //必须要有一个return，不然将一直尝试sdf(4\5\6...)的i=123,123,123...此时book123均已经等于1，将无限循环下去
    }

    for(i=1; i<=n; i++)
    {
        if(book[i] == 0)
        {
            a[i] = step;
            book[i] = 1;

            dfs(step+1); //执行下一步
            book[i] = 0; //将当前一种情况打印后，退一步
        }
    }
    return;
 }

 int main()
 {
     printf("输入1-9一个数字: ");
     scanf("%d", &n);

     dfs(1);

     return 0;
 }