无向图的邻接多重链表表示及其实现

"40. 蛤蟆的数据结构笔记之四十图的邻接多重链表表示实现.pdf" 在图论中，数据结构的选择对于高效处理图形数据至关重要。本文主要探讨了邻接多重表这一数据结构，它特别适用于无向图的存储。无向图的特点是任意两个顶点之间可能存在一条边，而这条边没有方向性。在邻接多重表中，每条边都会在以它所连接的两个顶点为头结点的链表中各出现一次，这样可以方便地进行某些特定操作，如标记已访问的边或删除特定边。 邻接多重表的结构与十字链表相似，由顶点表和边表组成。顶点表中的每个结点包含两部分：vertex域用于存储顶点信息，firstedge域指向第一条依附于该顶点的边。边表结点则更为复杂，包括mark域（用于标记边的状态，如是否已访问），ivex和jvex域（分别记录边连接的两个顶点在图中的位置），ilink和jlink域（分别指向依附于ivex和jvex的下一条边），以及info域（指向与边相关的信息，如边的权重或其他附加数据）。 创建邻接多重表的过程通常涉及以下步骤： 1. 打开数据文件，如"cmnet.txt"，用于读取图的顶点和边信息。如果文件无法打开，则程序会终止执行。 2. 读取图的顶点数和边数。这些信息通常是预先定义好的，或者从输入文件中获取。 3. 遍历顶点数，为每个顶点创建一个顶点表结点，并将其firstedge域设置为NULL，表示此时该顶点还没有关联的边。 4. 接下来，遍历边数，读取每条边的两个端点（ivex和jvex）。对于每条边，创建一个新的边表结点，设置对应的ivex和jvex域，并分配mark、ilink和jlink域。 5. 将新创建的边表结点插入到对应的顶点链表中，即ivex和jvex的firstedge域，通过ilink和jlink域连接相邻的边。 6. 完成所有边的插入后，关闭数据文件。 在邻接多重表中，由于每条边在两个顶点的链表中均有记录，所以对于无向图的操作，如遍历所有邻接顶点、查找边或者修改边的状态等，都变得相对直接。这种数据结构在处理无向图时，相比于邻接矩阵或其他数据结构，往往能提供更高的效率，特别是在边的数量远小于顶点数量平方的情况下。然而，对于有向图，邻接多重表可能不如邻接表那样直观和方便，因为有向图的边只连接到一个顶点，而不需要在两个顶点的链表中都有记录。