C++的深度优先搜索算法 |21xrx.com

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

2023-07-01 20:45:09 深夜i -- --

C++ 深度优先搜索算法

深度优先搜索(Depth-First Search，DFS)是一种常用的图形搜索算法，它可以用来解决许多计算机科学问题，如寻找图的连通性、寻找迷宫的路径、数独和八皇后问题等等。在C++中，我们可以通过递归函数实现DFS算法。

DFS算法的基本思路是依次访问图的各个节点，并在访问到某一节点时继续向下深度优先搜索，直到达到一个终止节点，然后沿着搜索路径回溯，直到找到一个未被访问的节点，再以这个节点作为起点继续搜索。具体操作可以通过以下步骤实现：

1. 初始化图中所有节点的标记位为“未访问”状态。

2. 从起点节点开始访问，并将其标记为“已访问”状态。

3. 依次递归访问与当前节点相邻的所有未访问节点，并将它们标记为“已访问”状态。若当前节点没有未访问的相邻节点，则返回到上一节点。

4. 重复第三步操作，直到找到终止节点或遍历完所有节点。

下面是一个简单的C++程序代码，它通过DFS算法在一个无向图中查找两个节点之间的路径。

#include

using namespace std;

const int MAXN = 100005;

vector G[MAXN]; //邻接表存储图

bool vis[MAXN]; //标记数组，记录每个节点访问状态

bool dfs(int u, int v){

vis[u] = true; //标记当前节点为已访问

if (u == v) return true; //当前节点为终止节点，返回true

for (int i = 0; i < G[u].size(); i++){ //遍历当前节点相邻的所有节点

int nxt = G[u][i];

if (!vis[nxt]){ //若相邻节点未访问，则进行递归搜索

if (dfs(nxt, v)) return true; //如果找到终止节点，返回true

}

return false; //当前节点没有未访问的相邻节点，返回false

}

int main() {

int n, m;

cin >> n >> m;

for (int i = 1; i <= m; i++){

int u, v;

cin >> u >> v;

G[u].push_back(v);

G[v].push_back(u);

}

int s, t;

cin >> s >> t;

bool flag = dfs(s, t);

if (flag) cout << "Yes" << endl;

else cout << "No" << endl;

return 0;

}

在上面的代码中，我们使用了邻接表来存储图，并使用一个bool类型的标记数组vis来记录每个节点的访问状态。在进行DFS搜索时，我们从起点节点开始访问，在访问每个节点时，都将其标记为已访问状态，并遍历其所有相邻的未访问节点。如果遇到终止节点，则返回true结束搜索。否则，继续寻找下一个未访问的节点进行递归搜索。最后，如果找到了两个节点之间的路径，输出"Yes"，否则输出"No"。

总的来说，DFS算法在计算机科学中有着广泛的应用，是一种经典且重要的算法。通过C++语言的支持，我们可以在编程中非常方便地实现DFS搜索算法，并得到期望的结果。

上一篇: idea打包java可执行jar包

下一篇: Node.js聊天应用程序

评论区

()

相似文章