图 (Graph)
图并不是现实世界中的一幅画, 例如
在计算机中, 图是一种数据结构. 图是计算机科学的一个概念, 在数学中也有对应的数学分之: 图论.
计算机中的图如果表示出来大概长成这样
可以把上图想象成一个社交网络, 网络中的每个圆表示一个User, User存在某种关系.
或者看作是一个城市群, 每个圆表示一个城市, 城市之间通过道路联通.
直观的从图片上看 有3个组成部分:
- 红色的圆
- 黄色的边
- 黑色的数字
更一般的叫法是:
- 顶点(Vertex)
- 边(Edge)
- 存储的数据(Data)
图的概念
- 顶点 (Vertex): 组成图最小的元素, 顶点可以包含数据. 一个图可以有多个顶点.
- 边 (Edge): 一般来说, 边连接着两个顶点, 因此一个图中也可以存在多条边
- 相邻顶点(Adjacency Vertex): 相邻顶点也叫顶点的度, 简单来说就是一个顶点通过边可以访问到的其他顶点的集合, 例如图中顶点0的相邻顶点是{2, 3}
有了这些概念, 在理解的基础上就可以对图做一个稍微正式点的定义了
图中的顶点集合用V表示, 边的集合用E表示, 一张图有若干顶点和相连接的边组成, 因此图G是由集合V和集合E组成, 可以表示为G(V,E)
简单图
上图中的图叫做简单图, 那什么样的图不叫简单图呢? 如下所示
在顶点0, 存在一个边, 这种边称之为 自环边(self-loop)
在顶点0和1之间, 除了之前那张图片上的一条边之外, 又多了一条边, 多出来的这条边称之为 平行边(parallel)
因此, 拥有自环边或平行边的图不是简单图.
图的分类
上面给出的图的示例属于最简单的无向无权图.
因为图的边可以附加一些信息(权), 以及边是可以有方向的, 因此图有两个大类:
- 有权图和无权图
- 有向图和无向图
进一步的组合可以分为:
- 有权有向图
- 有权无向图
- 无权有向图
- 无权无向图
不同种类的图有不同的作用, 在开始学习图算法的时候, 应先从最简单的无权无向图开始.
图的基本表示
通过图片可以很清楚的知道图的形状, 那么如何转换到计算机中表示呢?
对于这个问题, 有两种方式:
- 邻接矩阵
- 邻接表
这两种方式各有优缺点, 具体选择哪一种需要看场景
邻接矩阵
