【数据结构实验报告-图的遍历】一、实验目的
通过本次实验，掌握图的基本结构及其常见遍历方式，理解深度优先搜索（DFS）和广度优先搜索（BFS）算法的实现原理与应用场景。同时，提高对图在实际问题中的应用能力，为后续学习图论相关算法打下基础。
二、实验内容
本次实验主要围绕图的两种基本遍历方式进行实现与分析：
1. 深度优先搜索（DFS）：模拟人类探索路径的方式，尽可能深入地访问每个节点。
2. 广度优先搜索（BFS）：按照层次逐层扩展，先访问离起始点最近的节点。
实验中使用邻接矩阵或邻接表表示图，并分别实现DFS和BFS算法，输出遍历结果。
三、实验环境
- 操作系统：Windows 10
- 编程语言：C++ / Python（根据个人选择）
- 开发工具：Visual Studio / PyCharm / VS Code
- 实验平台：本地计算机
四、实验步骤
1. 图的表示
使用邻接矩阵或邻接表存储图的结构。邻接矩阵适用于稠密图，邻接表适用于稀疏图。本实验采用邻接表进行存储。
2. DFS算法实现
- 从某个顶点出发，访问该顶点。
- 递归或非递归地访问其所有未被访问的邻接顶点。
- 使用一个数组记录已访问的节点，防止重复访问。
3. BFS算法实现
- 从起始顶点开始，将其加入队列。
- 依次取出队首元素，访问其所有未被访问的邻接顶点，并将这些顶点入队。
- 直到队列为空，遍历结束。
4. 测试与调试
构建不同的图结构（如无向图、有向图），验证DFS和BFS的正确性。
五、实验结果
以一个简单的无向图为例，图的顶点集合为 {A, B, C, D}，边集为 {A-B, A-C, B-D, C-D}。运行DFS和BFS算法后，得到如下结果：
- DFS遍历顺序（以A为起点）：A → B → D → C
- BFS遍历顺序（以A为起点）：A → B → C → D
通过多次测试发现，DFS更适用于寻找路径或回溯问题，而BFS则适合最短路径查找等场景。
六、实验总结
通过本次实验，我深入了解了图的两种基本遍历方法，并掌握了它们的实现方式与适用场景。DFS具有较强的递归特性，适合处理树状结构；BFS则利用队列机制，更适合解决层次结构问题。此外，在编程过程中也提高了对图结构的理解和代码实现能力。
七、思考与改进
在实验过程中，我发现图的遍历算法在不同图结构下的表现可能有所差异。例如，对于有环图，DFS需要特别注意防止无限循环，可以通过设置访问标记来避免。未来可以尝试将图的遍历应用于实际问题中，如迷宫求解、网络爬虫等，进一步拓展其应用范围。
附录：部分代码示例（Python实现）
```python
邻接表表示图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
visited = set()
def dfs(node):
if node not in visited:
print(node)
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor)
def bfs(start):
queue = [start]
visited = set()
visited.add(start)
while queue:
current = queue.pop(0)
print(current)
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print("DFS遍历结果:")
dfs('A')
print("\nBFS遍历结果:")
bfs('A')
```
---
