邻接矩阵存储图的深度优先遍历pta

### 使用邻接矩阵存储图并进行深度优先遍历 对于使用邻接矩阵存储图并执行深度优先遍历的操作，在处理过程中，主要涉及两个方面：一是构建邻接矩阵表示的图结构；二是基于该结构实施DFS（Depth First Search）。通过这种方式可以有效地探索所有节点及其连接情况。 #### 构建邻接矩阵 假设有一个无向图G=(V,E)，其中V代表顶点集合而E则为边集。为了创建一个大小为n×n(n=|V|)的邻接矩阵`adjMatrix`用于描述此图： - 如果存在一条由i指向j的边，则设置`adjMatrix[i][j]=1`(或权重w_ij); - 否则设其等于0； 当涉及到有权重的情况时，可以用具体的权值代替上述条件中的1[^3]。 ```cpp // 初始化 n*n 的零矩阵作为邻接矩阵 vector<vector<int>> adjMatrix(n, vector<int>(n, 0)); ``` #### 深度优先遍历实现 一旦有了邻接矩阵形式的地图表达方式之后，就可以着手编写递归版本或是迭代版式的DFS算法了。这里给出一种常见的递归方法来完成这项工作: ```cpp void DFS(int v, bool visited[], const vector<vector<int>>& adjMatrix){ cout << "Visited vertex: " << v << endl; visited[v] = true; for (int i = 0; i < adjMatrix.size(); ++i){ if (!visited[i] && adjMatrix[v][i]){ DFS(i, visited, adjMatrix); } } } ``` 这段代码定义了一个名为`DFS`的过程接收三个参数——起始访问结点编号v、布尔型数组标记哪些结点已被访问过以及传入之前建立好的邻接矩阵。每当遇到未被访问过的相邻结点就调用自己继续深入下去直到不能再前进为止。 #### 完整示例程序 下面提供一段完整的C++代码片段展示如何初始化数据结构、填充测试案例的数据，并最终启动一次从特定起点出发的深度优先搜索过程。 ```cpp #include <iostream> #include <vector> using namespace std; void DFS(int v, bool visited[], const vector<vector<int>>& adjMatrix); int main(){ int n = 5; // 假设有五个顶点 // 创建并初始化邻接矩阵 vector<vector<int>> adjMatrix(n, vector<int>(n, 0)); // 添加一些假定存在的边到我们的图中... adjMatrix[0][1] = adjMatrix[1][0] = 1; adjMatrix[0][2] = adjMatrix[2][0] = 1; adjMatrix[1][3] = adjMatrix[3][1] = 1; adjMatrix[2][4] = adjMatrix[4][2] = 1; // 准备好记录已访问状态的空间 bool* visited = new bool[n]; fill_n(visited, n, false); // 开始于第一个顶点 DFS(0, visited, adjMatrix); delete[] visited; return 0; } void DFS(int v, bool visited[], const vector<vector<int>>& adjMatrix){ cout << "Visited vertex: " << v << endl; visited[v] = true; for (int i = 0; i < adjMatrix.size(); ++i){ if (!visited[i] && adjMatrix[v][i]){ DFS(i, visited, adjMatrix); } } } ```