1. 基本定义

  • 图是由一组顶点和一组能够将两个顶点相连的边组成的
  • 自环：一条连接一个顶点和其自身的边
  • 平行边：连接同一对顶点的两条边
  • 简单图：没有平行边或自环的图
  • 相邻：两个顶点通过一条边相连
  • 子图：一幅图所有边的子集（以及他们所依附的所有顶点）组成的图
  • 连通图：从任意一个顶点都存在一条路径到达另一个顶点

  • 有向图：我感觉暂时用不到

    2. 高级定义

  • 二分图：能将所有节点分成两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分

    • 二分图的应用场景很广泛
  • 邻接矩阵：V×V的（布尔）矩阵
  • 邻接表数组：一个以顶点为索引的列表数组，通常用于非稠密图（稀疏图）