数据结构 12.图

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。在图中的数据元素，我们称之为顶点（Vertex），顶点集合有穷非空。在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

图按照边的有无方向分为无向图和有向图。无向图由顶点和边组成，有向图由顶点和弧构成。弧有弧尾和弧头之分，带箭头一端为弧头。

图按照边或弧的多少分稀疏图和稠密图。如果图中的任意两个顶点之间都存在边叫做完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度。有向图顶点分为入度和出度。

图上的边或弧带有权则称为网。

图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复的叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称为强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称为强连通分量。

无向图中连通且n个顶点n-1条边称为生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

图的邻接矩阵的表示方式需要两个数组来表示图的信息，一个一维数组表示每个数据元素的信息，一个二维数组（邻接矩阵）表示图中的边或者弧的信息。

如果图有n个顶点，那么邻接矩阵就是一个n*n的方阵，方阵中每个元素的值的计算公式如下：

邻接矩阵表示图的具体示例如下图所示：

首先给个无向图的实例：

但是，如果我们需要表示的图是一个网的时候，例如假设有个图有n个顶点，同样该网的邻接矩阵也是一个n*n的方阵，只是方阵元素的值的计算方式不同，如下图所示： 这里的wij表示两个顶点vi和vj边上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面是具体示例，表示的一个有向网的图和邻接矩阵：

邻接表是图的一种链式存储结构。主要是应对于邻接矩阵在顶点多边少的时候，浪费空间的问题。它的方法就是声明两个结构。如下图所示：

https://blog.csdn.net/qq_40276310/article/details/80668401

实现步骤：

（1）访问初始顶点v并标记顶点v已访问。

（2）查找顶点v的第一个邻接顶点w。

（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。

（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。

（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步

搜索过程如下图所示，初始点是白色，探索点是灰色，终结点是黑色 下图展示了由深度优先搜索算法构造的树：

实现代码：

以上图为例进行深度优先搜索

实现步骤：

（1）顶点v入队列。

（2）当队列非空时则继续执行，否则算法结束。

（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。

（4）查找顶点v的第一个邻接顶点col。

（5）若v的邻接顶点col未被访问过的，则col入队列。

（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。

搜索过程如下图所示，初始点是白色，探索点是灰色，终结点是黑色

摘自[https://blog.csdn.net/qq_35644234/article/details/60870719]

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。 然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点， 然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。 Dijkstra算法示例演示 求下图，从顶点v1到其他各个顶点的最短路径 首先第一步，我们先声明一个dis数组，该数组初始化的值为： 我们的顶点集T的初始化为：T={v1}

既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果： ![https://img-blog.csdn.net/20170308150707766?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMzU2NDQyMzQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast] 因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。

然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图： 然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis[3]的值是最小的，所以把v4加入到集合T中，此时集合T={v1,v3,v5,v4},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：< v4,v6>,然后我们发现：v1–v5–v4–v6的长度为：60，而dis[5]的值为90，所以我们要更新dis[5]的值，更新后的dis数组如下图： 然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下： 因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为：

起点 终点 最短路径 长度 v1 v2 无 ∞ v3 {v1,v3} 10 v4 {v1,v5,v4} 50 v5 {v1,v5} 30 v6 {v1，v5,v4,v6} 60