请尽可能写出详细的注释
时间: 2024-11-09 21:26:58 浏览: 14
在C++中,编写带注释的代码有助于理解函数的工作原理和逻辑。以下是一个详细的示例,展示了一个用于查找无向图连通分量的小程序,包括了关键部分的注释:
```cpp
#include <iostream>
#include <vector> // 使用vector来存储数据
#include <unordered_set> // 用于跟踪已访问的节点
// 定义邻接表结构体,每个节点存储一个顶点及其相邻节点
struct Node {
int vertex; // 节点所连接的顶点编号
std::vector<Node*> neighbors; // 存储相邻节点的引用
};
// 图结构体,包含顶点数、邻接表和一个辅助集合,用于跟踪已访问的顶点
class Graph {
private:
int vertices; // 顶点总数
Node** adjacencyList; // 邻接表数组
std::unordered_set<int> visited; // 已访问的顶点集合
public:
// 构造函数
Graph(int verticesNum) {
this->vertices = verticesNum;
adjacencyList = new Node*[vertices]; // 初始化邻接表
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = nullptr; // 初始时,每个节点都指向NULL
}
}
~Graph() { // 析构函数,释放内存
delete [] adjacencyList;
}
// 添加边的功能,如果两个顶点已经存在,则视为无向边
void addEdge(int src, int dest) {
Node* srcNode = findNode(src); // 查找源节点
Node* destNode = findNode(dest); // 查找目标节点
if (srcNode && destNode) {
srcNode->neighbors.push_back(destNode);
destNode->neighbors.push_back(srcNode);
} else {
std::cout << "无效的顶点输入" << std::endl;
}
}
// 深度优先搜索,返回当前连通分量的顶点集合
std::vector<int> connectedComponentDFS(int start) {
std::vector<int> component; // 存储当前连通分量
visited.insert(start); // 标记起始顶点为已访问
Node* currentNode = findNode(start);
while (currentNode != nullptr) {
component.push_back(currentNode->vertex); // 将节点加入集合
for (Node* neighbor : currentNode->neighbors) {
if (visited.find(neighbor->vertex) == visited.end()) { // 如果邻居未访问,递归处理
dfs(neighbor->vertex, visited, component);
}
}
currentNode = currentNode->neighbors.back(); // 下一个待处理的节点
}
return component;
}
// 辅助函数,查找指定顶点的节点
Node* findNode(int vertex) {
if (vertex >= 0 && vertex < vertices) {
return adjacencyList[vertex];
}
return nullptr;
}
};
int main() {
// 创建一个Graph实例
Graph graph(5);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 0); // 示例:形成一个环
// 计算连通分量数量及输出
int numComponents = 0;
for (int i = 0; i < graph.vertices; i++) {
if (graph.visited.find(i) == graph.visited.end()) {
std::vector<int> component = graph.connectedComponentDFS(i);
numComponents++; // 分量数量加一
for (int node : component) {
std::cout << node << " ";
}
std::cout << "\n";
}
}
return 0;
}
```
阅读全文