C++ 深度优先搜索 生成全排列排列
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/07/22 19:37:38
C++ 深度优先搜索 生成全排列排列
如何用深度优先搜索(DFS)生成全排列?求代码和每句的详解
如何用深度优先搜索(DFS)生成全排列?求代码和每句的详解
![C++ 深度优先搜索 生成全排列排列](/uploads/image/z/20239862-14-2.jpg?t=C%2B%2B+%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2+%E7%94%9F%E6%88%90%E5%85%A8%E6%8E%92%E5%88%97%E6%8E%92%E5%88%97)
#include<cstdio>
#include<iostream>
using namespace std;
int a[1000],v[1000],n;
void print(){
for (int i=1;i<=n;i++) printf("%d ",a[i]); //将每位输出
puts(""); //换行
}
void DFS(int dep){
if (dep==n) print(); //如果搜到一个结果输出
dep++; //查找当前要处理位
for (int i=1;i<=n;i++) { //枚举当前位
if (v[i]) continue; //如果这个数之前被选过就跳过
v[i]=1; //选中当前位
a[dep]=i;//将当前位存入数组
DFS(dep);//搜索下一位
v[i]=0;//取消选中当前位
}
}
int main(){
scanf("%d",&n); //读入
DFS(0); //深搜
system("pause"); //暂停(查看结果)
}
#include<iostream>
using namespace std;
int a[1000],v[1000],n;
void print(){
for (int i=1;i<=n;i++) printf("%d ",a[i]); //将每位输出
puts(""); //换行
}
void DFS(int dep){
if (dep==n) print(); //如果搜到一个结果输出
dep++; //查找当前要处理位
for (int i=1;i<=n;i++) { //枚举当前位
if (v[i]) continue; //如果这个数之前被选过就跳过
v[i]=1; //选中当前位
a[dep]=i;//将当前位存入数组
DFS(dep);//搜索下一位
v[i]=0;//取消选中当前位
}
}
int main(){
scanf("%d",&n); //读入
DFS(0); //深搜
system("pause"); //暂停(查看结果)
}