ji-ben-gai-nian.md

基本概念

什么是图

图是一种非线性的数据结构，图中每个元素称其为顶点，顶点和顶点之间存在的关系称其为边。如下图所示。

图是一种数据结构，由顶点集和边集组成,表示为，其中代表每个顶点，代表每条边。

有向图与无向图

有向图

如果图中的边存在方向性，则称这样的边为有向边，包含有向边的图成为有向图。

无向图

无向图中的边都是没有方向的。

加权图与非加权图

加权图

图中的每条边都有一个实数与之相对应，称这样的图为加权图。在世纪场景中，权重可以代表距离或者两人之间的相似程度等，一般情况下认为各边上的权重代表定点之间的连接强度。

非加权图

非加权图与加权图相对应，非加权图认为各边上的权重是一样的。

连通图与非连通图

连通图

如果图中不存在任何孤立的结点，称这样的图为连通图。

非连通图

如果图中存在孤立的结点，称这样的图为非连通图。

二部图/二分图

二部图是一类特殊的图，设是一个无向图，如果顶点可分割为两个互不相交的子集，并且图中的任意一条边均有，或者，，则称图为一个二分图。二部图是一种十分常见的图数据结构，描述两类对象之间的交互关系，比如：用户和商品，作者与论文

邻居

如果存在一条边连接定点和，则称是的邻居，反之亦然。

顶点的度

与顶点相关的边的条数称为顶点的度。

图的表现形式

邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。设是具有个顶点的图，顶点序号依次为,则的邻接矩阵是具有如下定义的阶方阵：

• 表示顶点与顶点邻接，即与之间存在边
• 表示顶点与顶点不邻接，即与之间没有边

邻接表

度矩阵

度矩阵其中包含的信息为的每一个顶点的度，度矩阵:

拉普拉斯矩阵

给定一个有个顶点的图，其拉普拉斯矩阵被定义为，其中为图的度矩阵，为图的邻接矩阵，拉普拉斯矩阵:

关联矩阵

关联矩阵的定义如下

用关联矩阵存储图时，我们需要两个一维数组分别表示定点集合和边集合，需要一个二维数组表示关联矩阵。