### 数据结构图的遍历的图形演示课程设计报告
#### 一、需求分析
##### 1.1 程序的功能
本课程设计的主要目的是通过图形界面演示图的两种基本遍历方法：深度优先遍历（DFS）和广度优先遍历（BFS）。具体功能如下：
1. **图的创建**：程序支持手动输入图的节点和边来构建图的邻接矩阵表示。用户可以通过输入节点间的连接来创建图。
2. **图的输出**：程序能够以图形的形式展示构建好的图，包括节点的位置和连接关系。为了简化问题，节点位置固定，便于观察。
3. **深度优先遍历**：用户可以选择进行深度优先遍历，程序会按照深度优先的原则遍历图中的每一个节点，并在图形界面上以特定颜色或标记显示遍历顺序。
4. **广度优先遍历**：同样地，用户也可以选择广度优先遍历模式，程序将根据广度优先原则遍历图中的节点，并在界面上展示遍历过程。
##### 1.2 输入输出的要求
- **输入要求**：用户需要输入图中节点的数量和每个节点之间的连接情况。输入格式为（起点编号，终点编号），以（0, 0）作为结束标志。
- **输出要求**：
- 图形界面展示构建好的图结构，包括节点和边。
- 在进行深度优先或广度优先遍历时，动态展示每个被访问节点的状态，如高亮显示或改变颜色等。
#### 二、概要设计
##### 2.1 主函数功能模块图
- **主函数**：负责程序的整体运行逻辑，包括接收用户输入、调用图的创建函数、图的遍历函数等。
- **图的创建模块**：根据用户输入创建图的邻接矩阵表示。
- **图的遍历模块**：包括深度优先遍历和广度优先遍历两个子模块，分别负责图的这两种遍历方式。
- **图形界面模块**：负责图的可视化展示，包括原始图的绘制和遍历过程的动态展示。
##### 2.2 课题涉及的数据结构和数据库结构
- **图的表示**：使用邻接矩阵来表示图，其中矩阵元素表示节点间是否存在边。
- **辅助数据结构**：
- **栈**：用于深度优先遍历过程中保存当前路径上的节点。
- **队列**：用于广度优先遍历过程中保存待访问的节点。
- **标记数组**：用于记录节点是否已经被访问过，避免重复访问。
#### 三、详细设计
##### 3.1 采用 C 语言定义相关的数据类型
- **图的定义**：使用二维数组 `int adjMat[MaxVertexNum][MaxVertexNum]` 表示邻接矩阵，其中 `MaxVertexNum` 定义最大节点数。
- **节点状态标记**：使用布尔型数组 `bool visited[MaxVertexNum]` 来标记每个节点是否已被访问。
##### 3.2 写出各模块的类 C 代码算法
- **图的创建函数**：接收用户输入，构建图的邻接矩阵。
```c
void createGraph(int adjMat[][MaxVertexNum]) {
int start, end;
printf("请输入节点间的连接 (起点 终点)，以 (0 0) 结束：\n");
while (scanf("%d %d", &start, &end) == 2 && start != 0 && end != 0) {
if (start >= 0 && start < MaxVertexNum && end >= 0 && end < MaxVertexNum) {
adjMat[start][end] = 1; // 设置连接
}
}
}
```
- **深度优先遍历函数**：使用递归方式实现。
```c
void dfs(int adjMat[][MaxVertexNum], int v, bool visited[]) {
visited[v] = true;
printf("访问节点 %d\n", v);
for (int w = 0; w < MaxVertexNum; w++) {
if (adjMat[v][w] == 1 && !visited[w]) {
dfs(adjMat, w, visited);
}
}
}
```
- **广度优先遍历函数**：使用队列实现。
```c
void bfs(int adjMat[][MaxVertexNum], int start) {
bool visited[MaxVertexNum] = {false};
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
printf("访问节点 %d\n", v);
for (int w = 0; w < MaxVertexNum; w++) {
if (adjMat[v][w] == 1 && !visited[w]) {
visited[w] = true;
q.push(w);
}
}
}
}
```
##### 3.3 画出各函数的调用关系图、主要函数的流程图
- **调用关系图**：主函数调用图的创建函数，之后调用遍历函数。
- **流程图**：每个主要函数的流程图，如图的创建、DFS 和 BFS 的流程图。
#### 四、调试分析以及设计体会
##### 4.1 测试数据
- 示例图：6 个节点，节点间的连接情况如下：
- (0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 4)
##### 4.2 程序调试中遇到的问题以及解决问题的方法
- **问题**：在遍历过程中，有时会出现重复访问的情况。
- **解决方法**：确保在遍历前重置 `visited` 数组的所有元素为 `false`。
- **问题**：广度优先遍历过程中，队列的操作可能会出现异常。
- **解决方法**：仔细检查队列操作逻辑，确保正确使用队列。
##### 4.3 心得体会
- 通过本次课程设计，深刻理解了图的邻接矩阵表示方法及其遍历的基本思想。
- 学习了如何使用图形界面展示图的遍历过程，增强了编程实践能力。
- 发现了调试复杂程序的重要性，特别是在处理数据结构和算法问题时。
#### 五、使用说明
- 运行程序后，根据提示输入图的节点连接信息。
- 选择深度优先遍历或广度优先遍历。
- 观察图形界面中图的遍历过程。
#### 六、附件
- 代码实现细节。
- 图形界面截图。
#### 七、参考文献
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). _Introduction to Algorithms_. MIT Press.
- Sedgewick, R., & Wayne, K. (2011). _Algorithms_. Addison-Wesley Professional.
