一、邻接表存储无向图回顾
邻接表存储无向图
图中红色框住的部分，是B顶点与C顶点的边，我们可以看到在边表中被表示了两次，会导致删除效率比较低（需要遍历两个顶点进行边的删除）
二、无向图的存储结构邻接多重表法
2.1 邻接多重表法定义
邻接多重表法
顶点结构定义
- data：数据域，存放顶点数据
- firstedge：第一条边的指针
边表节点结构定义
- ivex：边的两个顶点其中一个顶点 i 的序号
- ilink：边的两个顶点其中一个顶点 i 的相连的下一条边
- jvex：边的两个顶点其中一个顶点 j 的序号
-jlink：边的两个顶点其中一个顶点 j 的相连的下一条边
-info：信息域，可以存放边的信息
-mark：标记域，可以存放标记信息
2.2 邻接多重表法示例
邻接多重表法示例
三、邻接多重表发C语言定义
邻接多重表法C语言定义
四、十字链表法与邻接多重表法对比
十字链表法与邻接多重表法对比
共同点
- 都是链式存储结构
- 边结构都需要存放info域来保存权重
不同点
- 十字链表法针对有向图
- 邻接多重表法针对无向图
- 十字链表法需要快速找到入边与出边，所以顶点结构需要两个边指针
- 邻接多重表法没有入边与出边之分，所以定点结构只需要一个指针
网友评论