邻接矩阵存储图的深度优先遍历 邻接矩阵表示图-深度-广度优先遍历

在计算机科学中，图是一种数据结构，用于表示对象之间的关系。图由顶点（vertices）和边（edges）组成，可以是有向的或无向的，可以包含权重或不包含。在处理图的问题时，存储结构的选择至关重要，其中一种常见的方式就是使用邻接矩阵。 邻接矩阵是一个二维数组，用于表示图中所有顶点之间的邻接关系。对于有向图，邻接矩阵的每个元素`A[i][j]`表示从顶点`i`到顶点`j`是否存在一条边。如果存在，`A[i][j]`通常赋值为1，不存在则为0。无向图的邻接矩阵是对称的，因为边`(i, j)`和`(j, i)`等价。 例如，对于图`G1`，其邻接矩阵`M1`表示的是： ``` 0 1 0 1 0 1 0 1 0 ``` 这意味着存在边`(1, 2)`，`(2, 1)`和`(2, 3)`。 对于无向图`G2`，其邻接矩阵`M2`是： ``` 0 1 1 1 0 1 1 1 0 ``` 这里边`(1, 2)`，`(1, 3)`，`(2, 1)`，`(2, 3)`，`(3, 1)`和`(3, 2)`都存在，因为无向图的边是双向的。 在C++或类似的编程语言中，邻接矩阵可以定义为如下结构： ```cpp struct Graph { VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vex_num, arc_num; // 图的当前顶点数和边数 GraphKind kind; // 图的种类标志（有向/无向） }; ``` 其中，`AdjMatrix`可以是一个`bool`或`int`类型的二维数组，根据是否需要存储边的权重来决定。 **深度优先遍历（DFS，Depth First Search）**是从一个顶点开始，尽可能深地探索图的分支，直到到达叶子节点或者回溯到没有未访问过的邻接点为止。在遍历过程中，可以通过访问标志数组`visited`来跟踪哪些顶点已经被访问过，防止重复访问。DFS通常采用递归实现，也可以使用栈辅助。 **广度优先遍历（BFS，Breadth First Search）**是从一个顶点开始，先访问所有距离起始点最近的顶点，然后再逐步访问更远的顶点。这需要用到队列来存储待访问的顶点。BFS可以有效地找到两个顶点间的最短路径（在无权图中）。 以图`G4`为例，如果从顶点`V1`开始，DFS会得到访问序列`V1, V2, V4, V8, V5, V3, V6, V7`，而BFS会得到`V1, V2, V3, V4, V5, V6, V7, V8`。 在实际应用中，DFS和BFS各有优势。DFS在某些情况下（如查找树的最小公共祖先，检测环）更为适用，而BFS常用于寻找最短路径问题（如二叉树的层次遍历，Dijkstra算法）。了解并灵活运用这两种遍历方法是解决图论问题的关键。