【图论】图的实现

四种实现

实现形式 优点 缺点
邻接矩阵 实现简单,可求任意顶点的出度和入度 在存储稀疏图时会造成空间浪费
邻接表 使用数组链表实现,不会造成空间浪费 不能同时求出任意顶点的出度和入度,除非同时构建邻接表和逆邻接表。对边进行操作时需要操作两次
十字链表 使用数组链表实现,不会造成空间浪费,可以求出某个顶点的入度和出度 对边进行操作时需要操作两次
邻接多重表 对边的操作进行了优化:操作边时由两次减少到了一次 删除操作较为复杂

你可能感兴趣的