C/C++ dfs()深度优先搜索实例理解

理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步如何做”则与“当下该如何做”是一样的。这里有一个典型的dfs模型的实例。全排列问题。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int a[10];
int book[10];//标记数组，记得进行初始化，0为还未进行，1为进行过了
int n;

void dfs(int step)
{
    if(step == n + 1){//判断边界
        for(int i = 1; i <= n; i++){
            printf("%d ", a[i]);
        }
        printf("\n");

        return;//返回之前的一步
    }

    //尝试每一种可能性
    for(int 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);
    memset(book, 0, 10);//初始化book数组
    dfs(1);
    getchar();getchar();
    return 0;
}