实验背景与目的
在计算机科学领域中，数据结构是解决实际问题的重要工具之一。其中，图作为一种非线性数据结构，在网络分析、路径规划、社交网络等多个应用场景中具有广泛的应用价值。本实验旨在通过构建图的邻接矩阵并对其进行遍历操作，深入理解图的基本原理及其实现方法。
邻接矩阵是一种常用的表示图的方式，它以二维数组的形式存储图中的顶点信息和边的信息。通过该方式可以高效地实现图的各种算法，如深度优先搜索（DFS）和广度优先搜索（BFS）。本次课程设计的目标在于掌握邻接矩阵的构建过程，并熟练运用两种遍历算法对图进行操作。
实验环境与工具
- 编程语言：C++
- 开发环境：Visual Studio Code
- 操作系统：Windows 10
- 其他依赖库：无特殊依赖库
实验步骤
1. 邻接矩阵的构建
首先定义一个二维数组来表示图的邻接矩阵。假设图中有n个顶点，则需要创建一个大小为n×n的二维数组。数组中的每个元素表示对应两个顶点之间是否存在边以及边的权重。
```cpp
include
using namespace std;
const int MAX = 100; // 最大顶点数
int adjMatrix[MAX][MAX]; // 定义邻接矩阵
int vertexNum; // 顶点数量
```
接下来，根据输入的数据填充邻接矩阵。例如，用户可以通过命令行输入顶点之间的连接情况，程序将这些信息记录到邻接矩阵中。
```cpp
void createAdjMatrix() {
cout << "请输入顶点数量: ";
cin >> vertexNum;
cout << "请输入邻接矩阵元素:\n";
for (int i = 0; i < vertexNum; ++i) {
for (int j = 0; j < vertexNum; ++j) {
cin >> adjMatrix[i][j];
}
}
}
```
2. 图的遍历
深度优先搜索(DFS)
深度优先搜索从某个顶点开始，沿着一条路径尽可能深地访问所有可达顶点，然后回溯继续探索其他未访问过的路径。以下是DFS的具体实现：
```cpp
bool visited[MAX]; // 记录顶点是否已被访问
void dfs(int v) {
visited[v] = true;
cout << v << " "; // 输出当前顶点
for (int w = 0; w < vertexNum; ++w) {
if (!visited[w] && adjMatrix[v][w] != 0) { // 如果顶点w未被访问且存在边
dfs(w); // 继续递归访问
}
}
}
```
广度优先搜索(BFS)
广度优先搜索则采用队列的方式来逐层访问图中的顶点。首先访问起点的所有相邻顶点，再依次访问下一层次的顶点。
```cpp
include
void bfs(int start) {
bool visited[MAX];
memset(visited, false, sizeof(visited));
queue
q.push(start);
visited[start] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
cout << v << " "; // 输出当前顶点
for (int w = 0; w < vertexNum; ++w) {
if (!visited[w] && adjMatrix[v][w] != 0) {
q.push(w);
visited[w] = true;
}
}
}
}
```
3. 测试与结果分析
为了验证上述代码的功能正确性，我们准备了一个简单的测试案例：
假设图由5个顶点组成，其邻接矩阵如下：
```
0 1 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 0 0 1
0 0 1 1 0
```
运行程序后，分别执行DFS和BFS操作，观察输出结果是否符合预期。
总结
通过本次课程设计实验，我们不仅掌握了图的邻接矩阵表示法及其基本操作，还加深了对图论相关概念的理解。邻接矩阵虽然占用较多内存空间，但在处理稠密图时效率较高；而DFS和BFS作为图的两大经典遍历方法，在许多实际应用中都发挥着重要作用。
未来的工作方向可以考虑优化算法性能或扩展更多高级功能，比如最短路径计算、最小生成树等。希望本次实验能够为后续的学习提供坚实的基础。
