73_图的存储结构（下）

关键词：邻接链表法、

0. 邻接矩阵法中残留问题

MatrixGraph无法动态添加/删除顶点

1. 基本思想

为了进一步提高空间使用率，可以考虑使用链表替换数组，将邻接矩阵变换为邻接链表。

2. 邻接链表法

• 图中的所有顶点按照编号存储于同一个链表中
• 每一个顶点对应一个链表，用于存储始发于该顶点的边

• 每一条边的信息包含：起点，终点，权值

  
  邻接链表法示意图
  邻接链表法示例
  ListGraph继承关系图
• 边数据类型的设计

struct Edge :  public Object
{
  int b;    // 起始顶点
  int e;    // 邻接顶点
  E data;    // 权值
  // ...
};

• 顶点数据类型的设计

struct Vertex : public Object
{
  V* data;    // 顶点数据元素值
  LinkList<Edge> edge;  // 邻接于该顶点的边
  // ...
}

• 动态增加/删除顶点：
  int addVertex()：增加新的顶点，返回顶点编号
  int addVertex(const V& value)：增加新顶点的同时附加数据元素
  void removeVertex()：删除最近增加的顶点

ListGraph.h

3. 小结

• 邻接链表法使用链表对图相关的数据进行存储
• 每一个顶点关联一个链表，用于存储边相关的数据
• 所有顶点按照编号被组织在同一个链表中
• 邻接链表法实现的图能够支持动态添加/删除顶点

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4