在许多应用中,由相邻的结点所表示的模型起到了关键的作用。为了描述这些问题,我们使用图:这种抽象的数据对象。 图由很多实际的用途:
- 地图
- 软件系统中模块关系:比如说JS中模块的相互引用、依赖关系。
- 社交网络
本节会依次学习四种重要的图模型:
- 无向图(简单连接)
- 有向图(连接有方向性)
- 加权图(连接带权值)
- 加权有向图(即带权值又有方向)
无向图
图是一组顶点和一组两个顶点的边组成。 图的表示:对于一个有V个顶点的图,使用0至V-1来表示各个顶点,使用v-w记法来表示连接v和w的边。
术语
关于图的一些术语:
- 路径是由边顺序连接的一系列顶点,比如u-v-w-h表示u-h的一条路径
- 连通图:一幅图从任意一个顶点都存在一条路径到达另一个任意顶点。
- 树是一副无环连通图。互不连通的树组成的集合称为森林。
- 图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。