在计算机科学中，图是一种非常重要的非线性数据结构，广泛应用于各种场合，如网络路由、社交网络分析、地图导航等。图由一系列的顶点（或称作节点）和连接这些顶点的边组成。在C++中，图的表示方法有多种，而本篇文章将重点介绍如何使用邻接矩阵来存储图，并通过实例来分析如何利用邻接矩阵实现图的广度优先遍历（BFS）和深度优先遍历（DFS）。
我们需要明确什么是邻接矩阵。邻接矩阵是一种用于表示图中顶点之间相邻关系的二维数组。对于一个有n个顶点的图，它的邻接矩阵是一个n×n的二维数组。如果顶点i与顶点j之间有一条边相连，则数组中的对应元素edge[i][j]设为1，否则设为0。在无向图中，邻接矩阵是对称的，即edge[i][j] = edge[j][i]。在有向图中，邻接矩阵则可能不对称。
接下来，我们将通过一个C++的实例来展示图的邻接矩阵存储以及如何进行广度优先和深度优先遍历。首先定义一个`GRAPH`结构体，其中包含顶点数组`vex`、邻接矩阵`edge`、顶点数量`n`和边的数量`e`。
```cpp
struct GRAPH {
int vex[MAX]; // 顶点数组，存储顶点信息
int edge[MAX][MAX]; // 邻接矩阵，存储顶点之间的连接关系
int n; // 顶点数量
int e; // 边的数量
};
```
`Create`函数用于根据用户输入的顶点数和边数，以及每条边连接的两个顶点信息，来初始化图的邻接矩阵。例如，若用户输入“0 1 1”，则表示顶点0和顶点1之间存在一条边，即在邻接矩阵中，edge[0][1]和edge[1][0]应被设置为1。
```cpp
void Create(GRAPH &G) {
// 初始化图的顶点和边的数量
G.n = ...; // 用户输入
G.e = ...; // 用户输入
// 初始化邻接矩阵的所有值为0
for (int i = 0; i < G.n; i++)
for (int j = 0; j < G.n; j++)
G.edge[i][j] = 0;
// 根据用户输入的边信息更新邻接矩阵
for (int k = 0; k < G.e; k++) {
int i, j;
cin >> i >> j; // 读取边连接的两个顶点
G.edge[i][j] = G.edge[j][i] = 1; // 设置对应矩阵值为1
}
}
```
在广度优先遍历（BFS）中，使用一个队列来记录待访问的节点。BFS从一个顶点开始，访问所有可达的顶点，直到所有顶点都被访问。为了防止重复访问，需要一个访问标记数组`visited`。
```cpp
void BFS(GRAPH &G, int k) {
queue<int> Q; // 定义队列，存储待访问的节点
G.visited[k] = true; // 标记起始节点为已访问
Q.push(k); // 将起始节点入队
while (!Q.empty()) { // 当队列不为空时进行循环
int u = Q.front(); // 取队首元素
Q.pop(); // 出队
cout << G.vex[u] << " "; // 访问节点
// 遍历所有顶点
for (int i = 0; i < G.n; i++) {
if (G.edge[u][i] && !G.visited[i]) { // 若存在边且未被访问
G.visited[i] = true; // 标记为已访问
Q.push(i); // 将未访问的邻居顶点入队
}
}
}
}
```
深度优先遍历（DFS）则利用递归来实现。从一个顶点开始，遍历其所有未访问的邻居节点，直到所有节点都被访问过。DFS不需要使用队列，但是需要调用递归函数。
```cpp
void DFS(GRAPH &G, int k) {
cout << G.vex[k] << " "; // 访问起始节点
G.visited[k] = true; // 标记为已访问
for (int i = 0; i < G.n; i++) {
if (G.edge[k][i] && !G.visited[i]) { // 遍历所有邻居
DFS(G, i); // 递归访问未访问的邻居节点
}
}
}
```
在`main`函数中，我们初始化`visited`数组，并创建一个`GRAPH`实例，然后调用`DFS`函数从顶点0开始进行深度优先遍历。
```cpp
int main() {
GRAPH G;
bool visited[MAX] = {false}; // 访问标记数组
// ... 初始化图G
// DFS遍历
DFS(G, 0); // 从顶点0开始DFS遍历
// 如果需要进行BFS遍历，可以重新初始化visited数组
// BFS遍历
BFS(G, 0); // 从顶点0开始BFS遍历
return 0;
}
```
广度优先遍历和深度优先遍历各有其特定的应用场景。广度优先遍历通常用于求解最短路径问题，因为它可以保证先访问到距离起点最近的节点。而深度优先遍历在搜索时深入到一条路径的尽头，适合用于检测图中是否存在环或求解拓扑排序等问题。对于复杂的图算法问题，如最短路径计算、最小生成树等，理解BFS和DFS两种遍历策略至关重要。
通过上述的实例分析，我们可以看到，C++实现图的邻接矩阵存储和遍历技巧在解决相关问题时非常实用。掌握这些技术不仅可以帮助我们在面试中解答算法题目，更能在实际开发中快速实现图相关的功能。
