DFS 全排列问题 C语言代码

深度优先搜索(DFS)是一种遍历算法，尽可能深地向子树中的结点搜索，直到达到一定的深度，再回溯到上层的结点，继续搜索未被访问的结点。

全排列问题

给定 4 个数 1 2 3 4，求他们所有可能的排列结果 。

代码

#include <stdio.h>
void dfs(int x);
int i;
int a[4];
int result[4] ;    //保存排列结果
int flag[4] ;      //标记 
int main(void){
	   
	for (i = 0 ; i <4; i++){
		a[i] = i+1;
		result[i] = 0;
		flag[i] = 0;
	}
	
	dfs(0);
	return 0;
}
void dfs(int x){
		
		if(x == 4){
			for(i = 0 ; i < 4 ; i++ ){
				printf("%d ", result[i]);
			}
			printf("\n");
			return ;
		}else{
			for(int i = 0 ; i < 4; i++){
				if(flag[i] == 0){
					result[x] = a[i] ;
					flag[i] = 1 ;
					dfs(x+1);
					flag[i] = 0 ;
				}
			}
		}
}
	

运行结果

代码解析

上面的代码中用数组 a[i] 存放要排列的 1 2 3 4， 用 result[ ] 表示排列的结果，flag 用于记录这个数字是否被访问过。

dfs 有一个通用的模板，如下所示。关键在于进入dfs之后首先要判断是否达到停止条件，没有的话就要考虑对当前这个结点做什么，做完之后要继续下一层的 dfs ，下一层结束后要把当前结点的标志重新标为0。在main()函数中调用 dfs（）时，括号里的参数是开始的层数，如 dfs(0) 指的是从第0层开始，而 dfs(1) 指深度为1的情况，这时候也就是有两个数排列好了。

void dfs(int x){
		
		if(达到停止条件){
			输出结果
			return ;   //返回
		}else{      //还要继续向下搜索
			for(int i = 0 ; i < 4; i++){
				if(flag[i] == 0){   //未被访问过，访问次数不限的话不写也行
					result[x] = a[i] ;   //排列结果中加上当前的结点
					flag[i] = 1 ;        //标记当前结点已访问
					dfs(x+1);            //继续搜索下一层
					flag[i] = 0 ;        //再把当前节点标记为未访问过
				}
			}
		}
}