7.2.4 无向图(网)的邻接多重链表存储表示

　　类似于有向图的十字链表，若将无向图中表示同一条边的两个结点合在一起，将得到无向图的另一种表示方法--邻接多重表。

　　例如，无向图G2的邻接多重表如下所示(忽略相关信息指针)：

　

无向图的邻接多重表存储表示
　　const MAX_VERTEX_NUM = 20;
　　typedef emnu {unvisited, visited} VisitIf;

　　typedef struct EdgeNode{ 　　　　// 边结点结构定义
　　　VisitIf mark; 　　　　　　　　　// 访问标记
　　　int ivex, jvex; 　　　　　　　　// 该边依附的两个顶点的位置
　　　struct EdgeNode *ilink, *jlink; // 分别指向依附这两个顶点的下一条边
　　　VRType weight; 　　　　　　　　 // 与弧相关的权值，无权则为0
　　　InfoType *info; 　　　　　　　　// 与该边相关信息的指针
　　} ;
　　typedef struct { 　　　　　　　// 顶点结点结构定义
　　　VertexType data;
　　　EdgeNode *firstedge;　　　　　　// 指向第一条依附该顶点的边
　　} VexNode;
　　typedef struct { 　　　　　　　// 多重链表结构定义
　　　VexNode adjmulist[MAX_VERTEX_NUM];
　　　int vexnum, edgenum;　　　　　　// 无向图的当前顶点数和边数
　　　GraphKind kind; 　　　　　　　　// 图的种类标志
　　} AMLGraph;

  

　　由于无向图的邻接表中每一条边有两个结点，给对图的边进行访问的操作带来不便。以无向图G2为例，当从顶点A出发访问了边(A,E)之后，为了下次不再对这条边进行访问，就需要找到表示这条边的另一个结点加上访问标志。由此可类似于有向图，只用一个结点表示一条边，即将该边的所有信息(边两端的两个顶点、与其中一个端点有相同端点的下一条边的信息等)放在一个结点中，由于无向图中的边是没有方向性的，因此所有有一个端点相同的边均链接在同一链表中，所以在顶点结点中只有一个链表的头指针。另一方面，因为每一条边有两个顶点，因此每个边结点都链接在两个链表中，但它们之间并不形成"十字"关系。