表 1 几种图的存储结构的比较
Tab. 1 The Comparsion of Several Graph for Storing Structures
| 名 称 | 实现方法 | 优 点 | 缺 点 | 时间复杂度 |
| 邻接矩阵 | 二维数组 | 1. 易判断两点间的关系 | 占用空间大 | O(n2+m*n) |
| 2. 容易求得顶点的度 | ||||
| 邻接表 | 链表 | 1. 节省空间 | 1. 不易判断两点间的关系 | O(n+m)或O(n*m) |
| 2. 易得到顶点的出度 | 2. 不易得到顶点的入度 | |||
| 十字链表 | 链表 | 1. 空间要求较小 | 结构较复杂 | 同邻接表 |
| 2.易求得顶点的出度和入度 | ||||
| 邻接多重表 | 链表 | 1. 节省空间 | 结构较复杂 | 同邻接表 |
| 2. 易判断两点间的关系 |