深度优先搜索（DFS）
2024-03-18 20:20:28
发布于：北京
22阅读
0回复
0点赞
汇总
深度优先搜索（Depth-First Search，DFS）是一种常见的图遍历算法，用于遍历或搜索图或树的节点。在DFS中，从起始节点开始，沿着一条路径尽可能深的搜索，直到到达叶子节点，然后回溯到上一个节点继续搜索。
DFS算法步骤：
-
访问当前节点：访问当前节点，并将其标记为已访问。
-
对当前节点的未访问邻居节点进行递归访问：对当前节点的所有未被访问过的邻居节点，依次递归执行DFS。
-
回溯：如果当前节点的所有邻居节点都被访问过，回溯到上一个节点。
示例代码：
让我们以一个简单的无向图的表示作为示例。假设有以下图：
A -- B
| |
C -- D
使用邻接表来表示这个无向图：（C++）
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
// 定义图的邻接表
unordered_set<char> graph[4] = {{'B', 'C'}, {'A', 'D'}, {'A', 'D'}, {'B', 'C'}};
bool visited[4];
// 深度优先搜索函数
void dfs(char node) {
cout << "Visiting node: " << node << endl;
visited[node - 'A'] = true;
for (char neighbor : graph[node - 'A']) {
if (!visited[neighbor - 'A']) {
dfs(neighbor);
}
}
}
int main() {
// 初始化visited数组
for (int i = 0; i < 4; i++) {
visited[i] = false;
}
// 从节点A开始深度优先搜索
dfs('A');
return 0;
}
在这个示例中，我们从节点A开始进行DFS。程序会按照深度优先的顺序访问各个节点，并输出每个节点的名称。通过递归地访问邻居节点，DFS能够探索整个连通图。您可以运行这段代码，并修改图的结构来验证DFS算法的工作原理。
这就是一个简单的深度优先搜索的示例，希望它能帮助您理解DFS算法的实现及其应用。如果您需要更多说明或有任何问题，请随时告诉我！
这里空空如也
有帮助，赞一个