什么是深度搜索,请结合C++代码详细解释一下
时间: 2024-03-02 12:50:42 浏览: 18
深度搜索(DFS)是一种用于图形和树形数据结构的算法,它通过递归的方式从起始节点开始搜索,直到找到目标节点或者到达没有未访问节点的末端节点为止。该算法通常使用栈来存储所有已经访问但未被处理的节点。
以下是一个使用C++实现深度搜索的例子,假设我们有一张无向图,用邻接矩阵来表示:
```C++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAX = 100;
int graph[MAX][MAX];
bool visited[MAX];
void DFS(int start) {
stack<int> s;
s.push(start);
visited[start] = true;
cout << "Visited node " << start << endl;
while (!s.empty()) {
int curr = s.top();
s.pop();
for (int i = 0; i < MAX; i++) {
if (graph[curr][i] && !visited[i]) {
s.push(i);
visited[i] = true;
cout << "Visited node " << i << endl;
}
}
}
}
int main() {
// Initialize graph
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
graph[i][j] = 0;
}
visited[i] = false;
}
graph[0][1] = graph[1][0] = 1;
graph[0][2] = graph[2][0] = 1;
graph[1][2] = graph[2][1] = 1;
graph[1][3] = graph[3][1] = 1;
graph[2][4] = graph[4][2] = 1;
graph[3][4] = graph[4][3] = 1;
// Start DFS from node 0
DFS(0);
return 0;
}
```
在这个例子中,我们使用邻接矩阵来存储图,其中非零值表示两个节点之间有一条边。我们从节点0开始进行深度搜索,并打印出每个访问过的节点。在搜索过程中,我们使用一个栈来存储所有已经访问但未被处理的节点,并逐一访问它们的邻居节点。如果一个邻居节点未被访问过,则将其加入栈中。
注意,在这个例子中,我们还使用一个布尔数组来记录每个节点是否已经被访问过。这是为了避免访问同一个节点多次,从而导致死循环。
总之,深度搜索是一种重要的图算法,常用于解决许多实际问题,如迷宫求解、最短路径问题等。