大家好，又见面了，我是你们的朋友全栈君。
1.判断图的连通性
图的遍历算法可以用来判断图的连通性。如果一个无向图是联通的，如果无向图是联通的，则从任一节点出发，仅需一次遍历就可以访问图中的所有节点。如果无向图是非联通的，则从某一节点出发，一次遍历仅能访问到该顶点所在联通分量的所有顶点，而对于图中其他联通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
2.遍历解答树
在问题求解时，对所有可能的问题解构成一颗树，而最优解或者符合要求的解就是该树的一条路径或一个节点。这种树称为解答树。
例1：通过深度优先搜索生成13的全排列
const int N = 13;
int d[N];//记录解
int v[N];//标记某个值是否被遍历过，没遍历过为0， 遍历过为1
int n;
void dfs(int depth){
if(depth == N){
for(int i = 0; i != n; i++){
cout<<d[i]<<" ";
}
cout<<endl;
return;
}
for(int i = 1; i <= n; ++i){
if(!v[i]){
v[i] = 1;
d[depth] = i;
dfs(depth+1);
v[i] = 0;
}
}
}
int main(){
cin>>n;
memset(v, 0, n);
dfs(0);
}例2：有1分、2分、5分、10分四种硬币，每种硬币数量无限，给定Target分钱，求有多少种组合可以组合成Target分钱？
int count = 0;//统计有多少种组合
int Target = 0;
int coin[4] = {
1,2,5,10};
int total = 0;
vector<int> res;
void dfs(int index){
if(total == target){
count++;
cout<<count<<endl;
for(int i =0 ; i < res.size(); ++i)
cout<<res[i]<<" ";
cout<<endl;
}
if(total > target) return;
for(int i = index; i < 4; ++i){
total += coin[i];
res.push_back(coin[i]);
dfs(i);
res.pop();
total -= coin[i];
}
}
int main(){
count = 0;
cin>>Target;
dfs(0);
cout<<count<<endl;
}**例3：**DFS解决1到n个自然数组成的集合的所有组合等问题。
const int N=100;
int number = 3;
int x[N];//解向量
void dfs(int cur_depth){
if(cur_depth >= number){
bool test = false;
for(int i = 0; i < number; ++i){
if(x[i] != 0){
cout<<i+1;
test = true;
}
}
if(test)
cout<<endl;
return;
}
x[cur_depth+1] = 0;
dfs(cur_depth+1);
x[cur_depth+1] = 1;
dfs(cur_depth+1);
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/136479.html原文链接：https://javaforall.net
