首页 > 代码库 > 深度优先搜索(dfs)
深度优先搜索(dfs)
关于深度优先搜索的总结；
1 dfs 的基本结构：
void dfs(int x){
if( x 超出边界){
return ;
}else{
for(遍历){
if(未访问过){
访问 ;
打上标记 ;
dfs(x + 1) ;
去掉标记 ; //极易忘记
}
}
}
return;
}
2 用dfs求全排列：
本来好好的，结果sizeof(pointer) 就完蛋了。神秘的内存错误，而且还能正常的跑出一个不正常的结果出来。
想了解sizeof这个小妖精的看这里 http://blog.csdn.net/wzy198852/article/details/7246836#comments
bool generatePermutations(int x){
int * flags = (int *)malloc(sizeof(int) * (x + 1));
int * ans = (int *)malloc(sizeof(int) * (x + 1));
memset(flags, 0, sizeof(int) * (x + 1)); // wo bei ken de hao ku a
memset(ans, 0, sizeof(int) * (x+1));
dfs(flags, ans, 1, x+1);
return true;
}
void dfs(int* book, int* ans, int step, int length){
if(step >= length){
for(int i=1; i<length; ++i){
cout << ans[i] << " ";
}
cout << endl;
return ;
}else{
for(int i=1; i<length; ++i){
if(book[i] == 0){
ans[step] = i;
book[i] = 1;
dfs(book, ans, step+1, length);
book[i] = 0;
}
}
}
return ;
}
3 我还要继续改下去
深度优先搜索(dfs)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。