6.2.5 图的基本操作

图接口包括增删顶点、增删边、判邻接、列邻居、取/设边权。复杂度依赖表示：矩阵判邻接 O(1)，邻接表枚举邻居 O(deg(v))；矩阵删顶点可能 O(V²)，表结构删顶点还需清除所有关联边。

手工状态

无向图删除顶点 v：先枚举 v 的所有邻居，从每个邻居表中删除 v，再移除 v 的表。若直接删 v 的表，其他表仍保存悬空边。

结构与代码

实现应维护顶点数、边数和唯一顶点标识。增无向边后边数只加1，尽管存储两条邻接记录；重复边策略需明确。

正确性依据

每个变更后保持不变量：所有边端点存在；无向邻接成对；边数与逻辑边一致；不存在禁止的自环/重边。

错解反馈

无向边数按两条记录加2；删顶点不清入边；顶点数组压缩后不更新边端点下标。

迁移训练

设计 removeVertex(v) 的三组测试：孤点、普通点、与所有点相连的点，并检查边数变化。