本文章介绍了利用邻接矩阵表示法实现图数据结构的深度优先和广度优先两种经典遍历算法的具体步骤及应用场景。
在计算机科学领域，图是一种用来表示对象间关系的数据结构。它由顶点（vertices）与边（edges）构成，并且可以是有向或无向的，同时可能含有权重或者不带权重。
处理图形问题时，选择正确的存储方式至关重要。邻接矩阵是常用的一种方法来储存这些信息。这是一个二维数组，用来展示图中所有顶点之间的连接情况。在有向图中，每个元素`A[i][j]`表示从顶点i到顶点j是否存在一条边；如果存在，则赋值为1，否则为0。对于无向图形而言，其邻接矩阵是对称的。
举个例子来说，在一个名为G1的图里，它的邻接矩阵M1是这样的：
```
0 1 0
1 0 1
0 1 0
```
这表明存在边（1,2），（2,3）和它们对应的对称边。
对于无向图形G2，其邻接矩阵M2如下所示：
```
0 1 1
1 0 1
1 1 0
```
这里包括了所有双向的连接：例如（1,2）、（2,1），（3,4）和（4,3）。
在C++等编程语言中，邻接矩阵可以这样定义：
```cpp
struct Graph {
VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vex_num, arc_num; // 当前的顶点数和边数
GraphKind kind; // 图类型标志（有向无向）
};
```
其中，`AdjMatrix`可以是布尔或整型二维数组，具体取决于是否需要记录权重信息。
**深度优先搜索 (DFS)** 是从一个给定节点开始尽可能深入地探索图的分支直到达到叶节点或者所有邻接点都已被访问。使用标记数组`visited`来追踪已访问过的顶点以避免重复访问。DFS通常通过递归实现，也可以借助栈结构完成。
**广度优先搜索 (BFS)** 则是从起始节点开始先遍历距离最近的所有节点再逐渐向外扩展。这需要一个队列用来存储待处理的节点信息。BFS在寻找无权图中的最短路径时特别有效。
以图G4为例，假设从顶点V1出发的话，DFS可能会产生访问序列V1, V2, V4, V8, V5, V3, V6, V7；而同样的条件下BFS则会生成顺序为：V1,V2,V3,V4,V5,V6,V7,V8。
实际应用中，DFS和BFS各有优势。例如，在查找树的最小公共祖先或检测环时，DFS可能更加适用；而在寻找最短路径问题上（如二叉树层次遍历、Dijkstra算法），则通常采用BFS方法来解决。
了解并灵活运用这两种搜索方式对于图论相关的问题来说至关重要。
5星
