【数据结构之图、图的存储、遍历、应用】

6.1图的基本概念

• 6.1图的基本概念

  图是由顶点（vertice）集和边（edge）集组成的，图又分为有向图、无向图、带权图，下图所示的是一个有向图

有向图：顾名思义就是具有方向的图，如上所示，顶点1指向顶点2，但是顶点2无法指向顶点1。

无向图：就是不区分方向的图，顶点1可以指向顶点2,同时顶点2也可以指向顶点1。

带权图：表示边带有权重的图，如下图所示

另外图中还包含路径这个概念，如上图v1到v7的路径有

v1->v2->v4->v7

v1->v2->v4->v5->v7

v1->v2->v5->v7

v1->v4->v7

v1->v4->v5->v7

以上这几种，如果要计算最短路径则需要将权重考虑在内，很显然v1->v7的最短路径是第四种方案，值为5。

6.2图的存储和操作

• 6.2图的存储和操作

  一、邻接矩阵

  
  邻接矩阵的性质
  空间复杂度: 0(|V|) —— 只和顶点数相关，和实际的边数无关

  对称矩阵：n阶矩阵的元素满足aij = aji,(0<=j, j<=n)；从矩阵的左上角到右下角的主对角线为轴，右上角的元素与左下角对应的元素对应全都是相等的。

  无向图的邻接矩阵一定是对称矩阵（并且唯一），因此，在存储时只需要存储上（或下三角）

  1.4的路径数目的意义
  若是 “平方”的意义
  关于a12和a24的解释：
  

  a12对应的是1（即第一行第二列），1说明从A->B有一条边
  a24对应的是1（即第二行第四列），1说明从B->D有一条边
  a12 乘 a24等于1（隐含的意思我们可以找到一条路径，从A->B->D 这一条路径是存在的）

  关于a13和a34的解释：
  a13对应的是0（即第一行第3列），0说明从A->C不存在路径
  a34对应的是0（即第三行第4列），0说明从C->D不存在路径

  关于A的平方[1][4]=1: 说明当A->D路径为2的时候，只能找到一条路径符合条件的
  是 “立方”的意义
  其实就是把平方在乘上原本的矩阵就可以成为三次方

  解释：
  取三次方的 “a14”为例子：
  1·0意思是：A平方的的第一行第一列对应的是1，乘上A的第一行第四列
  1·0意思是：1表示的是 从A->A长度为2的路径有1条
  0的意思是从A->D长度为1的路径有0条
  1·0=0，因此我们没办法把这两段路径凑齐来形成 A->D长度为3的路径
  a14对应的是1（即第一行第二列），1说明从A->B有一条边

  二、邻接表法（顺序+链式存储）
  2.1存储思路
  此前谈过孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少个孩子，也不会存在空间浪费问题，我们将这种数组与链表相结合的存储方法称为邻接表法
  

  2.2存储方法
  对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）

  每个链表上附设一个表头结点：

  邻接点域(advex)：与顶点vi邻接的点在图中的位置
  链域(nextarc)：指示下一条边或弧的结点
  数据域（info）：存储和边或弧相关的信息，如权值等
  头结点：

  数据域(data)：用于存储顶点vi的名或其他有关信息
  链域（firstarc）：指向链表中第一个结点之外
  在这里插入图片描述

  有向图与无向图的邻接实例：

2.3存储特点

三、十字链表（有向图）
3.1定义
十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧都有一个结点，对应于每个顶点也有一个结点

3.2十字链表性质

四、邻接多重表（无向图）

当要删除A与B相连的边的时候：

首先删除结点
可以看到接下来我们需要修改两个指针
上面的指针是指向与A相邻的边，下面的指针是指向与B相邻的边
删除A：则我们只需要在删除结点之前，顺着橙色方块，找到下一条边对应的是哪个结点即可
删除B：结点也一样，我们只需要通过绿色块，找到与绿色块相邻的边即可，则让B指向她即可

小结：

6.3图的遍历

• 6.3图的遍历
  从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）

  访问过的顶点打上标记，避免访问多次而不自知；可以通过设置一个访问数组visited[n]，n是图中顶点个数，初值为0，访问之后设置为1

  图遍历要避免因回路陷入死循环，通常有两种遍历次序方案：

  深度优先遍历
  广度优先遍历

  1、深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称DFS

如上图，如何从顶点A开始走遍所有的图顶点并作上标记？

从顶点A开始，始终向右手边走，注意，走到最后，还有一个I顶点没走。

深度优先遍历其实就是一个递归的过程，从图右边路径可以看出类似一棵树的前序遍历，确实如此。

从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径想通的顶点都被访问到。

非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

邻接矩阵深度优先遍历
邻接矩阵表示如下图：

总结：两个不同存储结构深度优先遍历算法

邻接矩阵是二维数组，要查找每个顶点的邻接点需要访问矩阵中的元素，因此需要O(n^2)的时间
邻接表做存储结构，需要时间取决于顶点和边的数量，所以是O(n+e)
显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

2、广度优先遍历
广度优先遍历（Breadth First Search），又称广度优先搜索，简称BFS。

深度优先遍历未必是最佳方案，它意味着要彻底查找完一个地方，然后才查找另一个地方。

DFS类似于树的前序遍历，BFS类似于树的层序遍历。

如上图所示，顶点A作为第一层，A的所有边顶点BF作为第二层，BF的所有边顶点CIGE作为第三层，依次类推。

总结
两种遍历时间复杂度是相同的，不同的是对顶点的访问顺序不同。

两种算法没有优劣之分，视不同的情况选择不同的算法。

深度优先更适合目标比较明确，以找到目标为主要目的的情况
广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

6.4图的应用

• 6.4图的应用

  1、最小生成树

  2、最短路径

  BFS算法

  迪杰斯特拉算法

  Floyd算法

  3、有向无环图

  4、拓扑排序

  

  5、逆拓扑排序

6、关键路径