假设有n个整数,分别是1~n,现在将这n个数进行排列

深度优先搜索的例题

假设有n个整数，分别是1~n，现在将这n个数进行排列，每个整数只能且一定要出现一次，且它们的全排列。

程序

www.noi.cn培训视频《深度优先搜索及其应用》里的例题。dfs(看见缩写总忍不住去猜一下涵义，deep-first-search)是一个递归的函数，其中利用book[11]做了一个标记，当有某个数被使用时，将对应的book数字中的值置为1，以避免数字重复。比如1被使用时，book[1]置1，2被使用时，book[2]置1。这里后面的book[i]=0;有点儿抽象，刚设了1怎么又置0了能，原因是其上方是一个递归函数，实际的执行顺序是等程序出结果后才后被置0。

#include<iostream>
using namespace std;

int a[11],book[11],n,sum=0;

void dfs(int t){
    if(t==n+1){
        sum++;
        for(int i=1;i<=n;i++)cout << a[i];
        cout << endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(book[i]==0){
            a[t]=i;
            book[i]=1;
            dfs(t+1);
            book[i]=0;
            //cout<<book[1] << " " << book[2] << " " << book[3] <<endl;
        }
    }
}

图解程序逻辑

简单画了张图帮助理解，程序的上半部分仅供输出结果，主逻辑在for循环内，当n=3的时候，for循环会产生3个分支，即a[1]分别等于1，2，3的时候，这3种情况又各自产生分支，我们来看一下头部的一个分支。

for(int i=1;i<=n;i++){
    if(book[i]==0){
    a[t]=i;
    book[i]=1;
    dfs(t+1);
    book[i]=0;
    //cout<<book[1] << " " << book[2] << " " << book[3] <<endl;
    }
}

dfs(2)的时候，前置book[1]=1，所以，i=1的时候if块内语句不会被执行，也就没有了后续递归，所以到这一步只会产生两路分支，分别是a[2]等于2，或者3的情况。依此类推，book[i]的可用值被逐一打标一直到dfs（4）输出该支线的结果，此时递归回溯，book[3]清零，book[2]清零，执行a[2]=3的分支。