一些术语
阿Q仅列出 术语,不进行详细解释
- G = (V,E); |V| != 0 (图不存在 空图,至少得有一个顶点)
- 有向图 弧<u,v> & 无向图 边(u,v)
- 简单图 & 多重图 (数据结构中仅讨论简单图)
- 完全图 (边数:无向图 C(n,2) = n(n-1)/2; 有向图 A(n,2)=n(n-1))
- 子图 (一个错误说法:图的边集的子集和顶点集的子集都构成其子图 ×)
- 连通 – 无向图 & 强连通 – 有向图
- 生成树 – 极小连通子图
- 度 (无向图)& 入度、出度 (有向图)
- 权、带权图 – 网
- 稠密图 & 稀疏图 (判断依据:|E| < |V|*log|V|,稀疏图)
- 路径、路径长度、回路(环)
- 简单路径、简单回路
- 距离 (u->v不存在路径,则距离为 ∞)
- 有向树(与树在逻辑上的区别: 树的边无方向;有向树的边有方向 – 双亲指向孩子)