C++算法之深度优先搜索算法

算法之深度优先搜索算法"/>

C++算法之深度优先搜索算法

深度优先搜索算法是图算法的一种，即DFS（Depth First Search）。其过程是对每个可能的分支路径深入直到不能再深入为止。下面会介绍深度优先搜索算法。

目录

1.框架

2.过程

2.1 步骤

2.2 解释

3. 例题

1.框架

void dfs(int u){//u:当前节点vis[u]=true;for(int& v:g[u]){//访问u连到的每个节点if(!vis[v]) dfs(v);}
}

2.过程

2.1 步骤

1、任选一顶点作始点 v ，访问该顶点
2、沿深度方向，依次遍历 v 的未访问邻接点，直到本次遍历结束
3、一次遍历完时，若有未访问顶点，任选一个未访问顶点作起始点，返回第二步

2.2 解释

下面用一张图片讲解深搜的运行过程：

从A出发，深度优先，右手优先，A→B，B→C，C→D，D→E，E→F，因为A走过了，所以F→G，B和D走过了，G→H，H可以通向的字母都走过了，寻找没有被走过的，走到I。

3. 例题

八皇后

【题目描述】

要在国际象棋棋盘（八行八列）中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）

【输入】

无输入。
【输出】

    若干行，每行一种放置方案；首先输出方案数，然后是八个数，表示每行皇后放置的列号。
【输出样例】
<1>1 5 8 6 3 7 2 4
<2>1 6 8 3 7 4 2 5
<3>1 7 4 6 8 2 5 3
<4>1 7 5 8 2 4 6 3

#include <iostream>
using namespace std;int selected[20];
int flag1[20];
int flag2[20];
int flag3[20];
int cnn;void dfs(int step);int main(){dfs(1);return 0;
}void dfs(int step){if(step==9){cout<<"<"<<++cnn<<">";for(int i=1;i<=8;i++){cout<<selected[i]<<" ";}cout<<endl;}else{for(int i=1;i<=8;i++){if(!flag1[i]&&!flag2[step+i]&&!flag3[i-step+8]){flag1[i]=1;flag2[step+i]=1;flag3[i-step+8]=1;selected[step]=i;dfs(step+1);flag1[i]=0;flag2[step+i]=0;flag3[i-step+8]=0;}}}
}

创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，如果喜欢我的文章，给个关注吧！

冰焰狼 | 文

如果本篇博客有任何错误，请批评指教，不胜感激 ！