简单图与多重图

图还可以按是否允许重复边、自环分为简单图和多重图。

1000

简单图

简单图满足两个条件：

  1. 不存在重复边。
  2. 不存在顶点到自身的边。

顶点到自身的边称为自环。简单图中不允许自环。

数据结构课程中，除非题目特别说明，通常默认讨论简单图。

多重图

若图中某两个顶点之间的边数多于一条，或者允许顶点通过同一条边和自己关联，则称为多重图。

多重图可以出现：

  • 重复边：同一对顶点之间有多条边。
  • 自环：某条边的两个端点是同一个顶点。

对比

类型 重复边 自环 常规数据结构题默认
简单图 不允许 不允许 是
多重图 允许 允许 否

后续若题目没有特别说明，计算边数上界、邻接矩阵、邻接表、遍历等内容时，都按简单图处理。