首页本关任务：实现 GraphMatrix.cpp 中的dfs操作函数，以实现深度遍历邻接矩阵存储的图功能。编程要求 dfs 初始条件：图存在操作结果：从顶点i出发的深度遍历邻接矩阵存储的图。输入输出格式请参见后续测试样例。

本关任务：实现 GraphMatrix.cpp 中的dfs操作函数，以实现深度遍历邻接矩阵存储的图功能。编程要求 dfs 初始条件：图存在操作结果：从顶点i出发的深度遍历邻接矩阵存储的图。输入输出格式请参见后续测试样例。

时间: 2024-12-13 08:25:22 浏览: 50

在C++中，实现深度优先搜索(DFS)遍历邻接矩阵存储的图，首先我们需要创建一个dfs函数，它接受两个参数：当前访问的顶点编号（i）和一个辅助数据结构，比如vector来记录已经访问过的节点。以下是基本的步骤： ```cpp #include <iostream> #include <vector> // 定义邻接矩阵的结构体或二维数组 typedef std::vector<std::vector<int>> GraphMatrix; void dfs(int i, const GraphMatrix& graph, std::vector<bool>& visited) { // 检查顶点是否已经被访问过 if (!visited[i]) { visited[i] = true; // 标记为已访问 // 遍历邻居节点 for (int j = 0; j < graph.size(); j++) { if (graph[i][j] == 1) { // 如果有边连接 dfs(j, graph, visited); // 递归访问邻居节点 } } } } // 主函数示例 int main() { GraphMatrix g = {{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}; // 代表三元邻接矩阵 std::vector<bool> visited(g.size(), false); // 初始化所有顶点未访问 int start_vertex = 0; // 起始顶点 dfs(start_vertex, g, visited); // 输出访问路径或检查结果 for (size_t i = 0; i < visited.size(); ++i) { if (visited[i]) std::cout << "Visited vertex " << i << std::endl; } return 0; } ``` 在这个例子中，我们首先初始化了一个邻接矩阵`g`，然后创建了`visited`向量来跟踪每个顶点是否被访问。`dfs`函数会遍历起始顶点的所有邻居，如果邻居未访问，则继续对其进行DFS。最后，在主函数中调用`dfs`并打印出被访问过的顶点。

阅读全文