数据结构与算法-图的定义与存储方式

一、图的基本概念与术语解析

1.图的定义与基本概念

图: G=(V,E)

V: 由有限且非空的顶点（数据元素）构成的集合

E: 由有限数量的边所组成的集合

1. 无向图: 图中所有边均不具备方向性

2. 有向图: 图中所有边均具有明确的方向性

3. 完全图: 图中任意两个顶点之间均存在一条边进行连接

4)【
4) 稀疏图: 边或弧数量极少的图(e<nlogn)

5. 稠密图: 边或弧数量较多的图

6. 网: 具有边或弧权重信息的图

7. 邻接: 在无向图中，两个顶点通过边相连；在有向图中，两个顶点通过弧相连(圆括号表示无向图，尖括号表示有向图)

若存在(Vi,Vj)，则Vi与Vj互为邻接点

若存在<Vi,Vj>，则Vi邻接到 Vj，而Vj邻接于 Vi

8. 关联(依附): 边或弧与顶点之间存在的联系

若存在(Vi,Vj)/<Vi,Vj>，则该边或弧被称作关联于 Vi