一、实验目的

本次实验的主要目的是通过实际编程操作，理解图的基本结构及其两种主要遍历方式：深度优先搜索（DFS）和广度优先搜索（BFS）。通过对图的遍历算法的实现与测试，加深对图在计算机科学中应用的理解，并掌握如何在程序中表示图结构，以及如何运用不同的遍历策略来访问图中的所有节点。

二、实验内容

1. 使用邻接矩阵或邻接表的方式构建一个无向图。

2. 实现DFS和BFS两种遍历算法。

3. 对图进行遍历，并输出遍历结果。

4. 分析两种算法的时间复杂度及适用场景。

三、实验环境

- 编程语言：C/C++ 或 Python

- 开发工具：Visual Studio Code / Dev-C++ / PyCharm

- 操作系统：Windows 10 / Linux

四、图的表示方法

在本实验中，采用邻接表的方式表示图。邻接表是一种较为高效的存储方式，尤其适用于稀疏图。每个顶点对应一个链表，链表中保存了与该顶点相邻的所有顶点。

例如，对于一个包含顶点A、B、C、D的无向图，若A与B相连，B与C相连，C与D相连，则邻接表如下：

```

A: B

B: A, C

C: B, D

D: C

```

五、算法实现

1. 深度优先搜索（DFS）

DFS算法从某个起始点出发，沿着图的边尽可能深入地访问未被访问的节点，直到无法继续为止，然后回溯到上一个节点，继续探索其他未访问的分支。

实现步骤如下：

- 初始化一个访问标记数组，记录各个顶点是否已被访问。

- 从起始顶点开始，递归或使用栈结构进行遍历。

- 访问当前顶点，并将其标记为已访问。

- 遍历当前顶点的所有邻接顶点，若未被访问则递归调用DFS函数。

2. 广度优先搜索（BFS）

BFS算法从起始点出发，逐层访问其邻接顶点，即先访问离起始点最近的顶点，再访问更远的顶点，以此类推。BFS通常使用队列结构来实现。

实现步骤如下：

- 初始化一个访问标记数组和一个队列。

- 将起始顶点入队，并标记为已访问。

- 循环处理队列中的顶点，每次取出一个顶点后，遍历其所有邻接顶点。

- 若邻接顶点未被访问，则将其入队并标记为已访问。

六、实验结果与分析

通过编写代码实现了DFS和BFS算法，并对一个简单的无向图进行了遍历测试。测试结果如下：

- DFS遍历顺序：A → B → C → D

- BFS遍历顺序：A → B → C → D

从结果可以看出，两种算法都能正确遍历整个图，但遍历顺序不同。DFS更偏向于“深入”访问，而BFS则是“横向”扩展。

时间复杂度方面，DFS和BFS均为O(V + E)，其中V为顶点数，E为边数。两者在不同应用场景下各有优势，例如DFS适合寻找路径或回溯问题，而BFS更适合寻找最短路径或层次遍历问题。

七、实验总结

通过本次实验，掌握了图的结构表示方法以及DFS和BFS两种基本的遍历算法。不仅提高了对图结构的理解，也增强了编程实践能力。同时，通过对比两种算法的执行过程，进一步认识到它们在不同场景下的适用性。

八、参考文献

- 《数据结构（C语言版）》严蔚敏 吴伟民

- 《算法导论》Thomas H. Cormen 等

- 相关网络资料及教学视频