图算法(一): 图的概念基本表示

图 (Graph)

图并不是现实世界中的一幅画, 例如

在计算机中, 图是一种数据结构. 图是计算机科学的一个概念, 在数学中也有对应的数学分之: 图论.

计算机中的图如果表示出来大概长成这样

可以把上图想象成一个社交网络, 网络中的每个圆表示一个User, User存在某种关系.

或者看作是一个城市群, 每个圆表示一个城市, 城市之间通过道路联通.

直观的从图片上看 有3个组成部分:

1. 红色的圆
2. 黄色的边
3. 黑色的数字

更一般的叫法是:

1. 顶点(Vertex)
2. 边(Edge)
3. 存储的数据(Data)

图的概念

1. 顶点 (Vertex): 组成图最小的元素, 顶点可以包含数据. 一个图可以有多个顶点.
2. 边 (Edge): 一般来说, 边连接着两个顶点, 因此一个图中也可以存在多条边
3. 相邻顶点(Adjacency Vertex): 相邻顶点也叫顶点的度, 简单来说就是一个顶点通过边可以访问到的其他顶点的集合, 例如图中顶点0的相邻顶点是{2, 3}

有了这些概念, 在理解的基础上就可以对图做一个稍微正式点的定义了

图中的顶点集合用V表示, 边的集合用E表示, 一张图有若干顶点和相连接的边组成, 因此图G是由集合V和集合E组成, 可以表示为G(V,E)

简单图

上图中的图叫做简单图, 那什么样的图不叫简单图呢? 如下所示

在顶点0, 存在一个边, 这种边称之为 自环边(self-loop)
在顶点0和1之间, 除了之前那张图片上的一条边之外, 又多了一条边, 多出来的这条边称之为 平行边(parallel)

因此, 拥有自环边或平行边的图不是简单图.

图的分类

上面给出的图的示例属于最简单的无向无权图.

因为图的边可以附加一些信息(权), 以及边是可以有方向的, 因此图有两个大类:

1. 有权图和无权图
2. 有向图和无向图

进一步的组合可以分为:

1. 有权有向图
2. 有权无向图
3. 无权有向图
4. 无权无向图

不同种类的图有不同的作用, 在开始学习图算法的时候, 应先从最简单的无权无向图开始.

图的基本表示

通过图片可以很清楚的知道图的形状, 那么如何转换到计算机中表示呢?
对于这个问题, 有两种方式:

1. 邻接矩阵
2. 邻接表

这两种方式各有优缺点, 具体选择哪一种需要看场景

邻接矩阵

邻接表