Question

讲了有向图的优化存储结构，对于无向图的邻接表，有没有问题呢？如果我们在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着，需要找到这条边的两个边表结点进行操作，这其实还是比较麻烦的。比如图7-4-11，若要删除左图的(v₀,v₂)这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较烦琐的。

图7-4-11

因此，我们也仿照十字链表的方式，对边表结点的结构进行一些改造，也许就可以避免刚才提到的问题。

重新定义的边表结点结构如表7-4-3所示。

表7-4-3

其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构。

我们来看结构示意图的绘制过程，理解了它是如何连线的，也就理解邻接多重表构造原理了。如图7-4-12所示，左图告诉我们它有4个顶点和5条边，显然，我们就应该先将4个顶点和5条边的边表结点画出来。由于是无向图，所以ivex是0、jvex是1还是反过来都是无所谓的，不过为了绘图方便，都将ivex值设置得与一旁的顶点下标相同。

图7-4-12

我们开始连线，如图7-4-13。首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同，这很好理解。接着，由于顶点v₀的(v₀,v₁)边的邻边有(v₀,v₃)和(v₀,v₂)。因此⑤⑥的连线就是满足指向下一条依附于顶点v₀的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。同样的道理，连线⑦就是指(v₁,v₀)这条边，它是相当于顶点v₁指向(v₁,v₂)边后的下一条。v₂有三条边依附，所以在③之后就有了⑧⑨。连线⑩的就是顶点v₃在连线④之后的下一条边。左图一共有5条边，所以右图有10条连线，完全符合预期。

图7-4-13

到这里，大家应该可以明白，邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，若要删除左图的(v₀,v₂)这条边，只需要将右图的⑥⑨的链接指向改为∧即可。由于各种基本操作的实现也和邻接表是相似的，这里我们就不讲解代码了。