Skip to content

在许多应用中,由相邻的结点所表示的模型起到了关键的作用。为了描述这些问题,我们使用图:这种抽象的数据对象。 图由很多实际的用途:

  • 地图
  • 软件系统中模块关系:比如说JS中模块的相互引用、依赖关系。
  • 社交网络

本节会依次学习四种重要的图模型:

  1. 无向图(简单连接)
  2. 有向图(连接有方向性)
  3. 加权图(连接带权值)
  4. 加权有向图(即带权值又有方向)

无向图

图是一组顶点和一组两个顶点的边组成。 图的表示:对于一个有V个顶点的图,使用0至V-1来表示各个顶点,使用v-w记法来表示连接v和w的边。 image.png

术语

关于图的一些术语:

  • 路径是由边顺序连接的一系列顶点,比如u-v-w-h表示u-h的一条路径
  • 连通图:一幅图从任意一个顶点都存在一条路径到达另一个任意顶点。
  • 是一副无环连通图。互不连通的树组成的集合称为森林
  • 图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。

image.png

表示无向图的数据类型