6.2.3 十字链表与邻接多重表

十字链表面向有向图：每条弧结点同时挂在弧尾的出边链与弧头的入边链，便于同时求入边和出边。邻接多重表面向无向图：一条边只建一个边结点，通过两个链接分别接入两个端点的边链，避免邻接表重复存边。

手工状态

弧 A→B 的结点记录 tail=A、head=B、下一条同尾弧、下一条同头弧。于是沿 A 出链枚举出边，沿 B 入链枚举入边。无向边 {A,B} 的一个边结点同时出现在 A、B 两条关联链。

结构与代码

删除边时必须从涉及的两条链都摘除。结构优势是边对象唯一，适合频繁修改边或需要边级属性；代价是字段多、实现复杂。

正确性依据

每个边/弧对象保存两个维度的链接，所以两种查询都不必全图扫描；唯一边对象保证修改权值只有一处。

错解反馈

只从一条链删除造成悬挂；把十字链表用于无向边仍区分弧头尾；邻接多重表重复建两份边结点。

迁移训练

说明删除 A→B 时需更新哪些链。答案：A 的出边链和 B 的入边链，并释放唯一弧结点。