详细讲一下每句代码的含义及用途#include <iostream> #include <queue> using namespace std; const int MAXN = 1000; struct Edge { int to, next; } edges[MAXN]; int head[MAXN], tot; bool vis[MAXN]; void addEdge(int u, int v) { edges[++tot].to = v; edges[tot].next = head[u]; head[u] = tot;}void dfs(int u) { vis[u] = true; cout << char(u + 'A') << " "; for (int i = head[u]; i != 0; i = edges[i].next) { int v = edges[i].to; if (!vis[v]) { dfs(v); } } } void bfs(int u) { queue<int> q; q.push(u); vis[u] = true; while (!q.empty()) { int x = q.front(); q.pop(); cout << char(x + 'A') << " "; for (int i = head[x]; i != 0; i = edges[i].next) { int v = edges[i].to; if (!vis[v]) { q.push(v); vis[v] = true; } } } } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { char u, v; cin >> u >> v; addEdge(u - 'A', v - 'A'); addEdge(v - 'A', u - 'A'); } dfs(0); cout << endl; for (int i = 0; i < n; i++) { vis[i] = false; } bfs(0); cout << endl; return 0; }
时间: 2024-03-10 21:47:16 浏览: 22
这段代码是一个简单的图遍历程序,实现了深度优先遍历(DFS)和广度优先遍历(BFS)两种方式。下面我们逐行解释每句代码的含义及用途。
```c++
#include <iostream>
#include <queue>
using namespace std;
```
这是头文件引入部分,分别引入了iostream和queue库,用于输入输出和队列操作。
```c++
const int MAXN = 1000;
```
定义了一个常量MAXN,表示最大的节点数为1000。
```c++
struct Edge {
int to, next;
} edges[MAXN];
```
定义了一个结构体Edge,用于存储图的边信息。
```c++
int head[MAXN], tot;
```
定义了两个全局变量,head数组用于存储每个节点的第一条边的编号,tot表示当前边的数量。
```c++
bool vis[MAXN];
```
定义了一个全局数组vis,用于标记每个节点是否被访问过。
```c++
void addEdge(int u, int v) {
edges[++tot].to = v;
edges[tot].next = head[u];
head[u] = tot;
}
```
定义了一个函数addEdge,用于添加一条从u到v的边,同时更新head和tot。
```c++
void dfs(int u) {
vis[u] = true;
cout << char(u + 'A') << " ";
for (int i = head[u]; i != 0; i = edges[i].next) {
int v = edges[i].to;
if (!vis[v]) {
dfs(v);
}
}
}
```
定义了一个函数dfs,实现深度优先遍历。首先标记当前节点已经被访问,输出节点名称,然后遍历当前节点所连的所有边,对于未被访问的节点递归调用dfs函数。
```c++
void bfs(int u) {
queue<int> q;
q.push(u);
vis[u] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
cout << char(x + 'A') << " ";
for (int i = head[x]; i != 0; i = edges[i].next) {
int v = edges[i].to;
if (!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
```
定义了一个函数bfs,实现广度优先遍历。首先将起始节点u入队,标记该节点已经被访问。然后依次取出队列首部的元素进行遍历操作,输出节点名称,并将其所连的所有未被访问过的节点入队并标记已访问。
```c++
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
char u, v;
cin >> u >> v;
addEdge(u - 'A', v - 'A');
addEdge(v - 'A', u - 'A');
}
dfs(0);
cout << endl;
for (int i = 0; i < n; i++) {
vis[i] = false;
}
bfs(0);
cout << endl;
return 0;
}
```
最后是主函数部分,首先读入节点数n和边数m,然后对于每条边,读入两个节点名称u和v,并调用addEdge函数添加从u到v和从v到u的两条边。接下来依次调用dfs和bfs函数进行遍历操作,最后输出一个空行。