# 图

## 图

非线性表结构。

## 基本概念

* 顶点：图中的元素称为顶点。
* 边：顶点与顶点之间的连接关系。
* 路径：从一个顶点到另一个顶点的顶点序列。包含两个顶点。
* 路径长度：路径上边的个数。
* 简单路径：顶点不重复出现的路径，称为简单路径。
* 环：第一个顶点和最后一个顶点相同的路径，称为回路或者环。
* 简单环：除了第一个和最后一个顶点，其余顶点都不重复出现的环，称为简单环。
* 度：跟顶点相连接的边的条数。
* 无向图：边没有方向的图称为无向图。
* 有向图：边有方向的图称为有向图。
* 入度：有向图中，有多少条边指向这个顶点。
* 出度：有向图中，有多少条边是以这个顶点为起点，指向其它顶点。
* 带权图：每条边都有一个权重的图。
* 简单图：在图中，若不存在某顶点到其自身的边，且不存在重复的边，则称之为简单图。
* 无向完全图：在无向图中，若任意两顶点之间存在边，则称之为无向完全图。边的个数为`n(n-1)/2`。
* 有向完全图：在有向图中，若任意两顶点之间存在方向相反的两条边，则称之为有向完全图。边的个数为`n(n-1)`。
* 连通图：无向图中，任意两个顶点都有路径相通，称为连通图。
* 强连通图：有向图中，任意两个顶点都有路径相通，称为强连通图。
* 连通网：带权重的连通图，称为连通网。
* 生成树：一个连通图的生成树，是指一个连通子图，它包含图中的所有n个顶点，但只有n-1条边。
* 最小生成树：连通网的所有生成树中，所有边权重和最小的生成树，称为最小生成树。

## 邻接矩阵存储方式

邻接矩阵使用的是二维数组。

* 对于无向图，如果顶点`i`和`j`之间有边，就将`A[i][j]`和`A[j][i]`标记为1。
* 对于有向图，如果有一条边，从顶点`i`指向顶点`j`，就将`A[i][j]`标记为1。
* 对于带权图，数组中存储的是权重。

**缺点：**

* 会造成空间浪费。无向图只需要对角线划分的一半。如果是稀疏图，顶点很多但是边不多，会很浪费存储空间。

**优点：**

* 存储方式简单。
* 获取值时非常高效。
* 运算简单，可以将图的运算转换成矩阵的运算。

## 邻接表的存储方式

有点类似于散列表。

* 对于无向图，每个链表存储的是与这个顶点连接的其它顶点。
* 对于有向图，每个链表存储的是这个顶点指向的其它顶点。

**缺点：**

* 查询顶点关系时，比较消耗时间。

**优点：**

* 比较节省空间。

**优化：**

可以将链表换成其它动态数据结构，如平衡二叉查找树、跳表、散列表或者有序动态数组等。
