6.2.5 图的基本操作
原书定位
印刷页P210起,对应PDF第222页。下文为目视整理的知识提要;完整内容见原书对照。
基本接口包括邻接判断、枚举邻边、增删顶点、增删边、取设边权,以及 FirstNeighbor、NextNeighbor。
同一接口在不同存储结构上的复杂度不同:矩阵查边快但扫邻点需整行;邻接表枚举邻边快但查指定边需搜索。删除顶点要处理其所有关联边;有向图既要删除出边,也要删除其他顶点指向它的入边。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P210起,对应PDF第222页。下文为目视整理的知识提要;完整内容见原书对照。
基本接口包括邻接判断、枚举邻边、增删顶点、增删边、取设边权,以及 FirstNeighbor、NextNeighbor。
同一接口在不同存储结构上的复杂度不同:矩阵查边快但扫邻点需整行;邻接表枚举邻边快但查指定边需搜索。删除顶点要处理其所有关联边;有向图既要删除出边,也要删除其他顶点指向它的入边。

