图概念
一些术语

阿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不存在路径,则距离为 ∞)
  • 有向树(与树在逻辑上的区别: 树的边无方向;有向树的边有方向 – 双亲指向孩子)

暂无评论

发送评论 编辑评论


上一篇
下一篇