#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;}逐行详细解释一下这段代码,以及这段代码是用来做什么的?
时间: 2023-12-06 09:03:24 浏览: 42
下面是逐行详细解释这段代码:
```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;
}
// Set up the graph
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); // 从节点0开始执行深度优先搜索
return 0; // 程序结束
}
```
这段代码实现了一个无向图,然后从节点0开始执行深度优先搜索,输出遍历的顺序。
首先,定义了一个图的邻接矩阵 `graph` 和一个数组 `visited` 来记录每个节点是否被访问过。
在 `DFS()` 函数中,定义了一个栈 `s` 来保存需要访问的节点。首先将起始节点0加入栈中,并标记为已访问。然后,不断从栈中取出一个节点,遍历它的所有邻居节点,将未访问过的邻居节点加入栈中,并标记为已访问。这样不断地取出栈顶节点,直到栈为空,表示遍历完成。
在遍历每个节点时,都会输出该节点的编号,以表示遍历的顺序。
在 `main()` 函数中,首先初始化了邻接矩阵和 `visited` 数组,然后手动指定了图中的边。接着,调用 `DFS()` 函数从节点0开始遍历整个图。
这段代码可以用来解决一些图论问题,例如查找连通子图、拓扑排序等。