图的邻接多重表存储
邻接多重表是一种针对无向图的存储。虽然在邻接表存储中可以方便地遍历无向图的顶点和边,但是无向图中相同的表结点存在于两个链表。若要对无向图的边进行操作,需要对两个链表中表示同一条边的表结点进行相同的操作,这其实还是比较麻烦的。因此,引出邻接多重表来存储无向图。
邻接多重表使用一个结点存储邻接表中的两个结点,这要求它要修改表结点结构:邻接多重表应该存储一条边的两个顶点编号,和两个指向不同链的指针,同时它还应有一个标志位,标志该表结点是否已被访问。邻接多重表的表结点如图1所示。
图1 邻接多重表表结点
其中flag域存储标志位,vertex1域和vertex2域存储一条边两个顶点的编号,link1域和link2域存储链接不同链表的指针。如果需要存储边相关数据,可以再设置一个数据域。
图2中给出了无向图G与G的邻接多重表存储示例。
图2 无向图G与G的邻接多重表存储示例
在图7-14中,所有依附于同一个顶点的表结点串联在同一链表中。因为一条边包含两个顶点,所以每一个表结点同时存在于这两个顶点的链表中。给图中的五个表结点编号为a~e,那么顶点v1~v4所在的链表包含的表结点分别为:
● v1:a->c->d
● v2:a->b
● v3:c->b->e
● v4:d->e
邻接多重表的顺序表部分与邻接表完全相同,在链表部分,邻接多重表将邻接表两个相同的表结点结合在一起,每个表结点只比邻接表多一个指针域和一个标志域。邻接多重表所需存储空间与邻接表大致相同,结构定义也相差无几。下面给出邻接多重表的数据结构定义。
//图的邻接多重表存储定义
#define MAX_VERTEX_NUM 200
//表结点
typedef struct EdgeNode
{
union //标志位
{
int visited;
int unvisited;
}flag;
int vexi; //边的两个端点
int vexj;
struct EdgeNode *ilink; //分别指向依附这两个顶点的下一条边
struct EdgeNode *jlink;
int info; //与边相关的数据
}EdgeNode;
//头结点
typedef struct VertexNode
{
int data; //顶点数据
EdgeNode *firstedge; //指向第一条依附该顶点的边
}VertexNode;
//结构定义
typedef struct
{
VertexNode adjmulist[MAX_VERTEX_NUM];
int n;
int e;
}AMLGraph;
邻接多重表存储时创建图的算法与其它几种存储方式创建图的算法大同小异,读者可以根据前面所学,自行写出邻接多重表存储创建图的算法。