图

定义：

   在一个具有 N 个顶点的无向完全图中，包含有 n*(n-1)/2 条边。有向完全图中，包含有 n*(n-1) 条边。

有向图： 就是各个顶点之间的边如果有向，则为有向图。有 n*(n-1)/2 条边。

无向图： 各个顶点之间的边没有方向箭头，则为无向图。有 n*(n-1) 条边。

有 n 个结点的无向图，该图至少应该有 n-1 条边才能确保是一个连通图。

那连通图是什么呢？
在无向图 G 中，我们从 v1 这个点到 v2 有路径的话，我们就说 v1 和 v2 是连通的。
说到这，那么连通图就好说了，  
如果我们在这个图中 随便找任意两点都是连通的，那我们就可以说 G 是连通图。

图的存储结构
邻接矩阵 和 邻接表表示法。


我们可以根据邻接矩阵 和 邻接表画出图。

根据邻接矩阵画图

定义：

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵

∞ 表示 的是计算机允许的，大于所有边上的权值的数。

而具体的数，就是该行该列中w [ i ][ j ] 从 i 到 j 的权值是多少

例如上图的 有向图中，
从 v1 到 v2 没有路径 所以为∞ 表示无法到达的意思
而 v1 到 v3 有路径且权值为 5 （就是该路径的 值 ，也就是权值）。

（注意：在有向图中,从一个顶点到另一个顶点有箭头指向才算有路径，而无向图不考虑方向）
（注意：无向图的邻接矩阵是关于矩阵的主对角线对称的）

使用邻接矩阵表示法的优缺点

优点：

	1. 便于判断两个顶点之间是否有边，根据 A[i][j] = 0 或 1 表示。
	2. 便于计算各个顶点之间的度。

度： 比如说 我们有个顶点 v ，那么和 顶点 有关联的 边的数目 ，就是 度。

这里 v1 的度为 2，
v2 的度为 2，
v3 的度为 3。
缺点：

	1.不便于增加和删除顶点。
	2.不便于统计边的个数，需要查找邻接矩阵所有元素才能统计完毕，时间复杂度为O(n^2)
	3.空间复杂度高。

（空间复杂度高（原因）：
例如我们有个 有向图，n 个顶点就要 nn 个单元储存边，
如果是个 无向图，因为无向图的邻接矩阵是对称*的，
所以 可以只存储其下三角（或者 上三角）的元素，
但无论采用哪种方式存储，临界矩阵的空间复杂度依然为 O(n^2) ，
这对于稀疏图来说 很浪费存储空间 ）

根据邻接表画图

而现在我们说的这个邻接表，可以解决邻接矩阵的浪费空间的缺点。
那么邻接表是什么呢？

定义：

邻接表(Adjacency List)：是图的一种链式存储结构。由部分组成

表头结点表：
由所有表头结点以顺序结构的形式存储，以便可以随机访问任意顶点的边链表。
data ： 数据域（存储数据的地方） 数据域通常用于存储顶点的名称，或者其他信息。
firstarc ：链域 （是用于指向链表中的第一个结点(就是 与顶点 v1 邻接的第一个邻接点)）。
v1 ，v2 ，v3 。。。是表头结点
边结点：
adjvex : 临界点域 （指的是顶点 vi 在邻接的点在图中的位置）
info ：数据域 （存储与边相关的信息）
nextarc:：链域 （指示下一条边的结点）
根据图：

可以画出邻接表：

这里 v1 是 0
v2 是 1 以此类推

邻接表中存储的是该结点可以到达哪一个结点。
例如 v1 可以到 v3 也可以到 v2 ，所以记为 2 ， 1；

边表（边链表）：
边表 是图的一种存储结构，用来描述图上的每一个点。对图的每个边进行编号，对图的每个顶点建立一个链表（n个顶点建立n个链表），第i个容器中的结点包含以顶点Vi为起点的所有边的编号。

在下面这个邻接表中:

表头结点为：

边表为：

逆邻接表：
逆邻接表则是，有多少个结点可以到达该结点。

例如：
v4 可以到达 v1 所以记为 3.

根据邻接表表示的优缺点：

优点：

	1.便于增加和删除顶点；
	2.便于统计边的数目按顶点表顺序可以得到所有边的数目，时间复杂度为O（n+e）；
	（n 表示 n 个顶点，e 表示有 e 条边）
	3.空间效率高；

一个 n 个结点 ，e 条边的图 G 。
若为无向图：则其在邻接表中有 n 个顶点表结点 和 2e 个边表结点( 2e 的原因是因为无向图没有限定固定方向所以对于两个点之间的路径可以双向通行，所以有 e 边就会有 2e 个边表结点)，
若为有向图：则其在邻接表中有 n 个顶点结点 和 e 个边表结点，
所以邻接表 和 逆邻接表 表示的空间复杂度为 O（n+e），适合用于表示 稀疏图。
但考虑到邻接表要附加链域，因此采用邻接矩阵表示法。
缺点：

	1.不便于判断顶点之间是否有边；
	2.不便于计算有向图中各个顶点的度；

图的两种遍历方式：

深度优先搜索（DFS）：

访问方式：从 v1 出发选择下一个未被访问的结点，v2 再以下一个结点为新结点，继续访问下一个结点，
重复此方式，直到找不到下一个未被访问的结点才结束。再从 v5 访问回 v1 发现还有未访问的结点，则继续重复上一个步骤。直至最终找不到未访问的结点，访问结束。

广度优先搜索（BFS）：

访问方式：从 v1 开始出发访问 v1 中未访问的结点，v2 和 v3 ，然后以 v2 和 v3 为新结点再分别访问这俩个结点中未被访问的结点。从图上看就是按层次关系依次向下遍历，直到最后一层，最后一个元素截至。

构造最小生成树

普利姆算法（加点法）适用于稠密图：

构成条件，每次寻找到达另一个顶点最小权值的一条只要不构成环，就可以加。否则找较小权值的顶点加。

克鲁斯卡尔法（加边法）适用于稀疏图：

`

构成条件，每次在图中找到最小权值的边，只要满足不构成环，且为能不构成环的最小值加上。

参考：《数据结构》（c语言版 第2版）