图的存储结构：邻接多重表

产生条件：邻接多重表的定义：邻接多重表的代码定义：删除：性能分析：十字链表与邻接多重表的对比

产生条件：

当用邻接矩阵法存储时：空间复杂度为O(|V|^2),太大

当用邻接表法存储时：一条边会重复存储两次，产生冗余

邻接多重表的定义：

顶点表节点：

1、data：顶点数据域2、firstedge:边表节点的头指针

边表节点：

1、ivex:该边的第一个端点2、ilink:与该端点相邻的下一个边表节点的指针3、jvex:该边的第二个端点4、jlink:与该端点相邻的下一个边表节点的指针5、info:权值6、mark:标记

邻接多重表的代码定义：

#define MaxVertexTypeNum 100typedef char VertexType;typedef int EdgeType;typedef struct ArcNode{//边表节点 int ivex,jvex;//边的俩个节点struct ArcNode *ilink , *jhink;//维护俩个节点的边表 //InfoType info; //权值 //bool mark;//标记位 }ArcNode;//边表节点的类型 typedef struct VNode{//顶点表节点 VertexType data;//顶点的数据 ArcNode *firstedge;//边表的头指针 }VNode;// 邻接表类型 typedef struct{//十字链表 VNode adjmulist[MaxVertexTypeNum];//所有结点的数据 int vexnum,arcnum;//节点数和边数 }ALGraph;//十字链表的类型

删除：

删除边AB：

删除节点E：

性能分析：

空间复杂度：O(|v| + |E|)

十字链表与邻接多重表的对比

十字链表：用于有向图，解决了无法快速找到一个顶点入边的问题

邻接多重表：用于无向图，解决了重复存储同一条边2次的问题

如果觉得《数据结构之图的存储结构：邻接多重表》对你有帮助，请点赞、收藏，并留下你的观点哦！