无向图的邻接多重表存储结构详解及其术语

邻接多重表是一种用于存储无向图的链式数据结构，它将顶点和边的信息组织在不同的节点中，使得图的表示更加灵活和高效。在无向图中，每个顶点（vertices）由一个顶点结点（vertex node）表示，该结点包含以下信息： 1. vertex：存放顶点的具体信息，如编号、特征值等，是图的基本组成单元。 2. firstedge：指针，指向第一个依附于该顶点的边结点，便于快速访问其关联的边。 3. mark：标记域，用来标识该边是否已经被处理过，用于遍历和算法优化。 4. ivex 和 jvex：分别表示边所连接的两个顶点的编号，这两个字段在无向图中是相同的，因为无向图的边是无序对，没有方向性。 5. ilink 和 jlink：指向下一条依附于顶点ivex和jvex的边，这样形成了一个双向链接结构。 这种存储方式允许对于每个顶点的所有边进行独立的管理，即使某条边有多条副本，也能通过边结点的指针轻松找到。无向图的邻接多重表可以有效地处理图中的重复边，并且在查询顶点的邻接顶点时，只需遍历第一个边结点的ilink和jlink即可。 邻接多重表与图的定义紧密相关，图通常由顶点集合V和边集合E组成，无向图的特点是边是无序对，没有方向性。例如，无向完全图意味着所有顶点之间都有一条直接边相连，而在实际应用中，如交通网络图和工程进度图中，边的权值（weight）赋予了图更丰富的含义，如距离、时间等。 无向图的邻接多重表结构对于图算法如深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（如Dijkstra算法）等都是非常有用的，因为它提供了方便的访问和遍历图的机制。理解并掌握邻接多重表是学习图论和算法设计的重要基础之一。