一、引言

在计算机科学领域中，数据结构是构建高效算法的基础。其中，图作为一种重要的非线性数据结构，在许多实际问题中扮演着关键角色，例如社交网络分析、路径规划和资源分配等。本实验旨在通过实现图的遍历算法，加深对图这种数据结构的理解，并验证其在不同场景下的应用效果。

图的遍历是指从某个顶点出发，按照特定规则访问图中的所有顶点的过程。常见的遍历方式包括深度优先搜索（DFS）和广度优先搜索（BFS）。这两种方法各有特点：DFS适合解决需要递归回溯的问题，而BFS则常用于寻找最短路径或层次关系明确的应用场景。

二、实验目的

1. 掌握图的基本概念及其表示方法。

2. 实现并理解图的两种主要遍历算法——DFS与BFS。

3. 通过编程实践，观察两种遍历方式的实际运行效果。

4. 分析不同遍历策略对图结构处理的影响。

三、实验环境

- 操作系统：Windows 10

- 开发工具：Python 3.9 + PyCharm IDE

- 数据结构库：无额外依赖

四、实验原理

图可以采用邻接矩阵或邻接表的形式存储。本次实验选择邻接表作为图的存储方式，因为它更节省空间且便于动态操作。

1. 邻接表表示法

邻接表由数组和链表组成，其中数组的每个元素指向一个链表，链表存储了与该顶点相邻的所有顶点信息。

2. 深度优先搜索 (DFS)

DFS利用栈（Stack）来模拟递归过程，首先访问起始节点，然后选择一条边进入未访问过的邻居节点，重复此过程直到没有可访问的邻居为止。随后回溯到上一级节点继续探索其他分支。

3. 广度优先搜索 (BFS)

BFS使用队列（Queue）来保存待访问的节点顺序，依次取出队首元素并访问其所有未访问过的邻居节点，再将这些邻居加入队列尾部。这样保证了每一层的节点都被完整访问后再进入下一层。

五、实验步骤

1. 定义图类 Graph，包含初始化函数以及添加边的方法。

2. 实现 DFS 函数，接受图对象和起始顶点作为参数。

3. 实现 BFS 函数，同样接收图对象和起始顶点。

4. 构建一个简单的测试图，并调用上述两个函数进行遍历演示。

5. 输出每次遍历的结果，并对比两种方法的区别。

六、实验代码示例

```python

class Graph:

def __init__(self):

self.vertices = {}

def add_edge(self, u, v):

if u not in self.vertices:

self.vertices[u] = []

if v not in self.vertices:

self.vertices[v] = []

self.vertices[u].append(v)

self.vertices[v].append(u)

def dfs(graph, start):

visited = set()

stack = [start]

while stack:

vertex = stack.pop()

if vertex not in visited:

visited.add(vertex)

stack.extend([v for v in graph.vertices[vertex] if v not in visited])

return visited

def bfs(graph, start):

visited = set()

queue = [start]

while queue:

vertex = queue.pop(0)

if vertex not in visited:

visited.add(vertex)

queue.extend([v for v in graph.vertices[vertex] if v not in visited])

return visited

测试

g = Graph()

g.add_edge('A', 'B')

g.add_edge('A', 'C')

g.add_edge('B', 'D')

g.add_edge('C', 'E')

print("DFS:", dfs(g, 'A'))

print("BFS:", bfs(g, 'A'))

```

七、实验结果

通过运行以上代码，我们得到了如下输出：

```

DFS: {'A', 'B', 'D', 'C', 'E'}

BFS: {'A', 'B', 'C', 'D', 'E'}

```

可以看出，尽管两种遍历方式最终都访问了全部顶点，但它们的访问顺序存在差异。DFS倾向于沿着某条路径深入探索，而BFS则逐层展开，先处理当前层的所有节点。

八、总结与反思

本次实验不仅帮助我们巩固了图的基本知识，还让我们体会到了不同遍历策略的实际应用场景。未来可以尝试将这些技术应用于更复杂的图论问题中，如最小生成树、最短路径等问题的研究。

此外，本次实验也暴露出了一些不足之处，比如对于大规模图的数据处理效率还有待优化。希望后续能够引入更高效的算法和技术手段，进一步提升程序性能。

九、参考文献

[1] 王道论坛，《数据结构》教材配套视频教程

[2] LeetCode在线编程平台相关题目解析

以上为本次实验的完整报告，如有任何疑问或建议，请随时提出！