无向图的邻接表存储与输出实现

本文主要介绍了如何使用邻接表来存储和输出无向图，并提供了相关的C++代码实现。 在图的表示方法中，邻接表是一种高效的数据结构，尤其适用于处理稀疏图（边的数量远小于顶点数量的平方）。无向图指的是图中的边没有方向，任何两个顶点之间可以双向相连。邻接表正是为了存储这种关系而设计的，它为每个顶点维护一个链表，链表中的元素表示与该顶点相邻的其他顶点。 邻接表的结构通常由以下几部分组成： 1. **顶点结构（VNode）**：每个顶点包含一个数据域（VertexType data）用于存储顶点的信息，以及一个指向第一条相邻边的指针（ArcNode* firstarc）。 2. **边结构（ArcNode）**：边结构包含一个相邻顶点的索引（int adjvex）和一个指向下一个相邻边的指针（struct ArcNode* nextarc）。 3. **图结构（ALGraph）**：整个图包含一个顶点数组（AdjList vertices），数组中每个元素都是一个顶点结构，同时包含了顶点数量（int vexnum）和边数量（int arcnum）。 在C++代码中，我们首先定义了这些结构类型，然后提供了一些操作函数： - **LocateVex**：这个函数用于找到指定顶点在邻接表中的位置，通过遍历顶点数组，将输入的顶点值与数组中的顶点数据进行比较，返回匹配的索引。 - **CreateALGraph**：这个函数实现了无向图的创建。首先，它接收用户输入的顶点数和边数。接着，让用户输入每个顶点的值，初始化邻接表。然后，对于每一条边，创建两个边结构，分别连接两个相邻的顶点。由于无向图的性质，当添加边(a, b)时，也需要添加边(b, a)。 在`CreateALGraph`函数中，`LocateVex`被用来找到边的起点和终点在数组中的位置，然后动态分配内存创建`ArcNode`对象，设置其`adjvex`属性并将其添加到相应顶点的链表中。 输出无向图可以通过遍历邻接表实现，对每个顶点，打印其数据，然后遍历其firstarc链表，输出所有相邻的顶点。 无向图的邻接表存储方式可以有效地节省空间，特别是对于稀疏图，因为只存储了实际存在的边。在处理图的遍历、查找路径等问题时，邻接表也具有较高的效率。