图论专有词汇解析
目录
图论中的基础知识介绍
时间复杂度
时间复杂度本质上是一个函数，它定性描述该算法的运行时间。
枚举
枚举就是一一列举图中各点之间的路径，在图中的点数量较少，邻接矩阵中0元素较多也就是通路较少的时候比较实用。
图
图是一种数据结构，它是由顶点集V与顶点间的关系集合E组成的，这里关系集合E通常用邻接矩阵或链表来表示。
稀疏图&稠密图
稀疏图与稠密图是通过“顶点数量与顶点间的关系数量”来区分的。数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图，反之边的条数|E|接近|V|²，称为稠密图，此外边数|E|等于|V|²的图为完全图。简单来说边越多，图就越稠密。
稀疏图与稠密图表示“所有点之间只有部分点之间存在联系”，而完全图表示“所有点之间均相互联系”。下图所示为稀疏图与稠密图：
度
一个顶点连接的弧或边的数目叫做这个点的度；
在有向图中，一个顶点所连接的指向这个点的弧或者边的数量叫做这个点的入度，同理，一个顶点所连接的背向这个点的弧或者边的数量叫做这个点的出度；（出度+入度=度）
针对于有向图中V3来说，V3的出度为1，入度为1，因此V3的度为2；
针对于无向图中V2来说，V2的度为3.
度与边的关系
无向图：
度的总数 / 2=边的总数
有向图：
度的总数=边的总数
在有向图中，任意两个顶点有路径就叫做连通图，若任意两点之间均有路径则可被称为强连通图；弱连通是有向图去掉方向之后任意两点之间连通才叫弱连通。
生成树
连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点和n-1条不构成回路的边。
这里若以A为起点，A->B->D->A就是一个生成树，而且它也是一条简单路径。
图的邻接矩阵
无向图的邻接矩阵
由于无向图路径为双向的而且正反向权值相同，因此矩阵为对称方阵；
每一行或者每一列1的个数代表着该点所连接的弧或者边的个数，即顶点的度；
当我们对邻接矩阵中1的个数进行求和时，我们对一条无向路径算了两次，因此图中边的数量为各个点度的总和的一半；
邻接矩阵中1或者0与0-1规划中的0或者1很相似，代表着点与点之间联系的有或无。
有向图的邻接矩阵
由于有向图路径为单向的，因此矩阵不是对称矩阵；
第i行中1的个数为第i点的出度，第i列中1的个数为第i点的入度；
邻接矩阵中1的个数为图中边或者弧的数目；
网的邻接矩阵
其实这里的网就可以直观地表示顶点之间的关系，只不过这里的关系被量化了用权重来表示。
网的邻接矩阵如下：
网与图的区别
图单纯地表示点与点之间路径的通断关系，但是网不但表示了点与点之间路径的通断关系，也表示了点与点之间的量化关系。
图的关联矩阵
无向图的关联矩阵
关联矩阵用来表示图中每个结点与每条边的关系，是描述图中结点与边关联的矩阵。一个图的关联矩阵描述了这个图的所有顶点和所有边的关联关系，不同于邻接矩阵研究结点之间的关系。
关联矩阵的特点：
① 每一列都只有两个1，代表着每一条无向边关联着两个顶点；
② 每一行的1代表着一个顶点的度，此外，若一行中无一个1，那么这个点是孤立顶点；
③ 有相同顶点的无向边对应相同的列元素。
有向图的关联矩阵
有向图的关联矩阵拥有的特点：
① 每一行非0元素的个数为该顶点的度，其中，-1的个数代表出度，1的个数代表入度，此外，若一行中无一个非零元素，那么这个点是孤立顶点；
② 每一列的非0元素一共为2个（如果自环的话，仅为一个-2），代表路径两端的两个端点，且有相同顶点的无向边对应相同的列元素。
参考
关联矩阵详解：
https://wenku.baidu.com/view/9476691f2e60ddccda38376baf1ffc4ffe47e232.html