[ data ] 数据结构之图结构的要点梳理

图结构定义

图结构是数据元素呈多对多关系，就是任意两个元素存在这样的关系。如果用一个公式来表示就是由顶点集合和顶点之间的关系集合组成的一种数据结构。

Graph = ( V , E ) ;

E1 = { ( X , Y ) | X , Y < V } 边的合集 （ < 号是表示包含）

E2 = { ( X , Y ) | X , Y < V } 弧的合集

无向图

使用公式表示无向图：

N = { V, E } , V = { 0, 1, 2 , 3, 4, 5 } , E = { ( 0, 1 ), ( 0, 2 ) ( 0, 4 ), ( 0, 5 ), ( 1, 2 ) ( 2, 3 ), ( 3, 4 ), ( 2, 4 ) ( 5, 3 ), ( 5, 4 ) }

画出的图为：

另：在无向图中还有一种叫无向完全图，指的是任意两点都有连接。

它的边的数量是： 1/2(n(n-1))；

连通图和连通分量

连通图指的是两个点的连接。

连通分量指无向图中的极大连通分量，且连通图就是无向图。一个无向非连通图会有多个的连通分量，举例：

在这两个例子中，一个无向非连通图就有两个连通的分量。

有向图

使用公式表示有向图：和无向图优点不同的是，有向图的标记是使用 < x, y > 的一个 arc ，且 x 为弧尾，y 弧头。

N = { V, E } , V = { 0, 1, 2 , 3, 4 } , E = { < 0, 1 >, < 1, 2 >, < 0, 3 >, < 0, 4 >, < 2, 4 >, < 3, 2 > }

画出的图为：

强连通图和强连通分量

强连通图指的是两个点之间有弧线。

强连通分量指有向图中的极大连通分量（有去有回），且连通图就是有向图。一个有向图会有多个的强连通分量，举例：

在这两个例子中，一个有向图就有两个强连通的分量。

另：在无向图中还有一种叫有向完全图，指的是任意两点都有两条弧。

路径

路径指的是从一个顶点到另一个顶点的所有方式，以无向和有向图的例子来看，从 0 到 3 的路径分别是，如图：

无向图 0 - 3 的路径是：

1. 0 - 1 - 2 - 3
2. 0 - 2 - 3
3. 0 - 4 - 3
4. 0 - 5 - 4 - 3
5. 0 - 2 - 4 - 3 有向图 0 - 3 的路径是（需要根据弧的指向） ：
6. 0 - 3 只有一条，原因是 3 的入度只有一个，而且是从 0 开始的。

简单路径

指的点不重复出现的一个路径，以上图的无向图为例，0 - 3 的简单路径就是

0 - 5 - 4 - 3

环路径

顾名思义就是一个环，起点和终点保持一致即可。

0 - 1 - 2 - 3 - 4 - 5 - 1

生成树

一个连通图的生成树是一个极小的连通图。核心就是最多的点，最少的边。一个由 n 个点的生成树有且仅有 n - 1 条边。

生成森林

有向图的生成树是一个由若干个树组成

有向树是一个只有一个顶点且入度为 0 其余点的入度为 1 的有向图。

7 和 9 入度都是 0 。

图的存储结构

邻接矩阵

邻接矩阵实质上是一个二维数组，对于不带权图，1表示两个顶点相连接的弧或者边，以 0 表示不邻接。

A【i】【j】 = ...... ;

以下图为例：

无向图和有向图他们的邻接矩阵分别对应的是

从矩阵上来看，很明显无向图的连接矩阵是对称的，而有向图的矩阵是非对称的。

邻接表

邻接矩阵实质上是一个二维数组 + 链表，他是在每个节点中有一个下标指向，还是以刚才的图作为例子，加上下标。

他们的邻接表分别对应的是：

无向图是按下标记，有向图是按出度，其中还有一个叫逆邻接表，逆邻接表是按入度的方式来，和邻接表相反。

图的遍历

从图的某一点开始，访问图中的其余顶点且每个点至少访问一次。

深度优先搜索 DFS

原理是从某个点向下查找，当到达末端时，返回向上一个节点查找是否还有未找到的节点，有则从这个节点向下查找，如果没有则再向上一个节点重复刚刚的操作。

深度优先搜索的实现核心是使用堆栈的方法。

他的过程是

第一步 ：1 - 2 - 4 - 8 - 5

第二步，回退(弹出) ：5 - 8 - 4 - 2 - 1

第三步 ：3 - 6

第四步，回退(弹出)：6 - 3

第五步 ：7

所以，最后的结果是 1 - 2 - 4 - 8 - 5 - 3 - 6 - 7 。

注意，这个例子有点像树，但是实际上他是图，因为树的前提是一个节点有且只有一个双亲，这里的 8 是有了两个双亲，所以他不满足树的条件。

广度优先搜索 BFS

广度优先搜索实质上是一个分层搜索，将一层节点查询完之后再向下一层几点开始查找，这种方法说明他没有回退的情况。

广度优先搜索的实现核心是使用队列的方法。

以深度优先搜索的图为例子，他的过程是： 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 。

最小生成树

最小的生成树意思就是最多的点和最少的边，n 和 n- 1 条边，同时不能产生回路且各边上的权值总和最小。

实现最小生成树有两种算法一种是普里姆算法，另一种是克鲁斯卡尔算法。

以这个为例子

普里姆算法

普里姆算法就是找点再找边再找点依次重复。

结果就是 1 - 4 - 6 - 2 - 3 - 5 （找点 算法）

克鲁斯卡尔算法

克鲁斯卡尔是不需要起点的，他是根据最小的边开始查找其余的边。

结果就是 2 - 3 - 3 - 3 - 7（找边 算法）

最短路径

最短的路径指的是图中的所有点他们之间的距离，或者说是某一点到任意一点的最小距离。

狄杰斯特拉（Dijkstra）算法

这个算法的思想就是，找到点与点之间的最小距离的边且只走这一步，之后再从这个点开始找最小距离的边同时也是只走一步，这个时候更新点与点之间的数据，然后继续在往下走。

其中，两点相连的直接记录权值，如果两点之间没有连接的计算为无穷大。

用一个例子来说明：

第一轮 N1: 从 0 开始，记录到达各点权值，若没有直接到达的边记录为 无穷大。

第二轮 N2: 从第一轮中得出，最小的是边指向 4 ，那么就从 4 开始 。4 到 2 ，也就是 0 - 4 - 2，10 + 50 = 60 。更新数值，其余不变。

第三轮 N3: 从第二轮中得出，由于 4 已选 ，那最小的是边指向 3 ，那么就从 3 开始 。3 到 2 ，也就是 0 - 3 - 2，30 + 20 = 50 。更新数值，其余不变。

第四轮 N4: 从第三轮中得出，由于 4，3 已选 ，那最小的是边指向 2 ，那么就从 2 开始 。0 到 2 ，没有连接，但是上一轮的指向是 50 ，那么就是 0 - 2 - 1 ，50 + 10 = 60 。更新数值，其余不变。

第五轮 N5: 数值不变，不更新。

这个就是最终结果

拓扑排序

拓扑排序的作用是可以得知每个点的优先级，而拓扑排序就是适用于有向无环图。

拓扑排序的算法思想是，在有向图中选一个没有前驱的顶点且输出也就是入度为0点的点，删除他的边和弧。重重上述操作，直到所有的点输出。

举例：

输出 0 ，输出 1 ， 输出 3 ， 输出 2 ， 输出 4。

数据结构不一定都可以在项目中实际应用，但也可以作为了解。下次看到的时候心里也大概知道这是一个什么样东西，需要使用了再深入了解方法。