C++使用DFS（深度优先）遍历邻接矩阵（源代码）

邻接矩阵是一种用于表示图的数据结构，其中图的顶点被表示为一个一维数组，而矩阵的行和列表示图中的顶点，矩阵中的元素则表示顶点之间的边的关系。在无向图中，如果顶点i和顶点j之间存在一条边，则矩阵中第i行第j列的元素和第j行第i列的元素都为1（或其他表示存在的值）；在有向图中，如果顶点i有一条指向顶点j的边，则矩阵中第i行第j列的元素为1。 邻接矩阵存储图的特点： 1. **直观性**：邻接矩阵可以直观地表示图中所有顶点之间的连接关系。 2. **空间复杂度**：对于包含n个顶点的图，邻接矩阵需要n*n的空间来存储，因此当图很稀疏（边数远小于n^2）时，邻接矩阵可能会浪费大量空间。 3. **时间复杂度**：判断两个顶点之间是否存在边的时间复杂度为O(1)，因为可以直接访问矩阵中的相应元素。 ### C++ 使用 DFS（深度优先）遍历邻接矩阵 #### 邻接矩阵概述 邻接矩阵是一种常用的数据结构，用于表示图中各顶点之间的连接关系。它通过一个二维数组来存储图的信息，其中行和列代表图中的各个顶点，而数组中的每个元素表示顶点间的边的存在与否。在无向图中，如果顶点i和顶点j之间存在一条边，则矩阵中第i行第j列的元素和第j行第i列的元素都为1（或其他表示存在的值）。在有向图中，如果顶点i有一条指向顶点j的边，则矩阵中第i行第j列的元素为1。 邻接矩阵具有以下特点： 1. **直观性**：邻接矩阵能够直观地表示图中所有顶点之间的连接关系，使得数据结构易于理解和实现。 2. **空间复杂度**：对于包含n个顶点的图，邻接矩阵需要n*n的空间来存储。这在图非常稀疏（即边的数量远小于n^2）的情况下可能会造成大量的空间浪费。 3. **时间复杂度**：判断两个顶点之间是否存在边的时间复杂度为O(1)，因为可以直接通过访问矩阵中的相应元素来实现这一点。 #### 图的遍历方法 图的遍历是图论中的一个重要概念，主要涉及两种基本方法：深度优先搜索（DFS）和广度优先搜索（BFS）。 1. **深度优先搜索（DFS）**：从某个顶点开始，尽可能深地搜索图的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直持续到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程。整个进程反复进行直到所有节点都被访问为止。 2. **广度优先搜索（BFS）**：从图的某一顶点出发，首先访问起始顶点，然后依次访问起始顶点的所有未被访问过的邻接顶点，再从这些邻接顶点出发依次访问它们的邻接顶点，如此进行下去，直到图中所有已被访问过的顶点的邻接顶点都被访问到，且图中尚存在未被访问过的顶点为止。 #### DFS 的 C++ 实现 下面是一段使用C++实现DFS遍历邻接矩阵的代码示例。该示例展示了一个包含5个顶点的无向图，并通过递归方式实现了深度优先搜索。 ```cpp #include <iostream> #include <vector> using namespace std; void DFS(vector<vector<int>>& graph, int v, vector<bool>& visited) { visited[v] = true; cout << v << " "; for (int i = 0; i < graph.size(); ++i) { if (graph[v][i] && !visited[i]) { DFS(graph, i, visited); } } } int main() { // 邻接矩阵表示：0与1、2相连，1与0、2、3相连，2与0、1、3、4相连，3与1、2、4相连，4与2、3相连 vector<vector<int>> graph = { {0, 1, 1, 0, 0}, {1, 0, 1, 1, 0}, {1, 1, 0, 1, 1}, {0, 1, 1, 0, 1}, {0, 0, 1, 1, 0} }; vector<bool> visited(graph.size(), false); // 初始化访问状态为false cout << "Depth First Search starting from vertex 0: "; DFS(graph, 0, visited); return 0; } ``` ### 分析与总结 此代码段展示了如何使用C++实现DFS遍历邻接矩阵的过程。具体来说，它包括以下几个步骤： 1. **初始化图**：通过一个二维数组`graph`表示无向图的邻接矩阵。 2. **记录访问状态**：使用一个布尔类型的`visited`数组来跟踪每个顶点是否已经被访问。 3. **DFS 函数实现**：该函数采用递归的方式实现深度优先搜索，从给定的顶点开始，遍历所有相邻的且未被访问过的顶点，并继续递归这一过程。 4. **主函数调用**：从顶点0开始执行DFS，并打印出遍历的顶点顺序。 通过这种方式，我们不仅能够有效地遍历图中的所有顶点，而且还可以直观地观察到DFS算法的工作原理及其对邻接矩阵的应用。此外，这种实现方式简洁明了，易于理解，是学习图遍历算法的一个很好的例子。