十字链表、邻接多重表、边集数组

十字链表、邻接多重表、边集数组 1. 十字链表

• 十字链表把邻接表和逆邻接表整合在了一起，这样既容易找到以Vi为尾的弧，也容易找到以Vi为头的弧，从而容易求出顶点的出度和入度。
• 事件复杂度是和邻接表相同的。

顶点表结点结构：

边表结点结构：

2. 邻接多重表

边表结构：

其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点iVex的下一条边，jlink指向依附顶点jVex的下一条边。

3. 边集数组

边集数组是有两个一维数组构成，一个是存储顶点的信息，另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。

详解