图的遍历：深度优先与广度优先

"本实验是关于图的基本操作，主要涉及数据结构中的图理论及其实现。实验目标包括巩固图的基本知识，熟悉图的存储结构，以及掌握深度优先遍历（DFS）和广度优先遍历（BFS）算法。实验内容要求以邻接表为存储结构，对连通无向图进行遍历，并根据用户指定的节点开始输出遍历序列。实验还提供了特定的测试数据，包括8个顶点和若干条边的信息。在实现过程中，涉及的主要函数有构建邻接表、查找顶点、获取邻接点等。源程序中包含了队列的初始化和判断队列是否为空等辅助功能。" 在图论中，图是一种抽象的数据结构，用于表示对象之间的关系。图由顶点（Vertex）和边（Edge）组成，边连接两个顶点，表示它们之间存在某种联系。在本实验中，我们关注的是无向图，即边没有方向，可以从一个顶点到另一个顶点双向移动。 图的存储结构主要有邻接矩阵和邻接表两种。邻接矩阵使用二维数组存储图中所有顶点对之间的关系，而邻接表更适合于稀疏图（边的数量远小于顶点数量的平方），它为每个顶点维护一个链表，链表中的元素表示与其相邻的顶点。 深度优先遍历（DFS）是一种递归的搜索策略，从起始顶点开始，沿着一条路径深入探索，直到达到叶节点或回溯到未访问的邻接顶点。在邻接表中实现DFS，通常使用栈或递归来完成。广度优先遍历（BFS）则是从起始顶点开始，逐层访问所有邻接顶点，常使用队列来实现。 实验中定义的`ArcNode`结构体代表边，存储了相邻顶点的索引和指向下一个边的指针。`VNode`结构体表示顶点，包含数据和指向相邻顶点链表的指针。`ALGraph`结构体存储整个图的信息，包括顶点数组、顶点数和边数。 `LocateVex`函数用于查找指定顶点在邻接表中的位置，`FirstAdjVex`获取指定顶点的第一个邻接点，`NextAdjVex`用于在邻接表中找到下一个邻接顶点。这些函数对于遍历图至关重要，因为它们帮助我们按顺序访问图的结构。 在实现DFS和BFS时，通常需要一个标志数组（如`visited[]`）来跟踪已访问的顶点，防止重复访问。源代码中还包括了队列的初始化和判断队列是否为空的函数，这是BFS的核心部分。 通过这个实验，学生不仅可以理解图的基本概念，还能实际操作，从而加深对图的存储结构和遍历算法的理解。这将有助于他们在后续的编程和算法设计中更好地处理图相关的问题。