[数据结构] 图与图上的算法

图

在数据结构中，图（Graph）是由一组节点和一组边组成的数据结构。节点表示图中的元素，边表示节点之间的关系。图可以用于表示各种实际问题，如社交网络、路线规划、电路设计等。

图可以分为有向图和无向图两种类型。有向图中的边是有方向的，表示从一个节点到另一个节点的单向关系；无向图中的边是无方向的，表示两个节点之间的双向关系。

图中的节点可以有权值，表示节点之间的距离或代价。有权图可以用于表示各种实际问题，如最短路径、最小生成树等。

图可以用多种方式来表示，如邻接矩阵、邻接表等。

邻接矩阵是一种二维数组，用于表示节点之间的关系。邻接矩阵的行和列分别表示图中的节点，矩阵中的元素表示节点之间的边。

在邻接矩阵中，如果节点i和节点j之间有边相连，则矩阵中的第i行第j列元素为1；否则，该元素为0。如果图是有权图，则矩阵中的元素可以表示边的权值。

邻接矩阵的优点是可以快速地判断两个节点之间是否有边相连，以及边的权值。

邻接矩阵的缺点是空间复杂度较高，需要存储所有节点之间的关系，即使节点之间没有边相连。因此，邻接矩阵不适用于表示稀疏图，即节点之间的边比较少的图。

邻接表是一种用于表示图的数据结构，它是由一组链表和一组节点组成的。每个节点表示图中的一个元素，每个链表表示一个节点的邻居节点。

在邻接表中，每个节点包含两个部分：一个是节点本身的信息，如节点的编号、权值等；另一个是指向邻居节点的指针。每个链表表示一个节点的邻居节点，链表中的每个元素表示一个邻居节点，包含两个部分：一个是邻居节点的信息，如节点的编号、权值等；另一个是指向下一个邻居节点的指针。

邻接表的优点是可以用较少的空间来表示稀疏图，即节点之间的边比较少的图。此外，邻接表可以快速地访问一个节点的邻居节点，以及判断两个节点之间是否有边相连。

邻接表的缺点是无法快速地判断两个节点之间的边的权值。

弗洛伊德算法（Floyd Algorithm），也称为插点法，是一种用于求解最短路径的动态规划算法。该算法可以在有向图或无向图中，计算任意两个节点之间的最短路径。

弗洛伊德算法的基本思想是，通过不断地插入中间节点，逐步缩小两个节点之间的距离，直到找到最短路径。具体来说，算法的步骤如下：

初始化距离矩阵D，其中D[i][j]表示节点i到节点j的距离。如果节点i和节点j之间有边相连，则D[i][j]为边的权值；否则，D[i][j]为无穷大。
对于每个中间节点k，依次更新距离矩阵D。具体来说，对于每对节点i和节点j，如果从节点i到节点j经过中间节点k的路径比直接从节点i到节点j的路径更短，则更新D[i][j]为更短的路径长度。
重复步骤2，直到所有中间节点都被考虑过为止。
最终得到的距离矩阵D即为任意两个节点之间的最短路径。

弗洛伊德算法的时间复杂度为O(n^3)，其中n为节点数。

该算法的优点是可以处理带负权边的图，缺点是空间复杂度较高，需要存储距离矩阵。

Dijkstra算法是一种用于求解最短路径的贪心算法，可以在有向图或无向图中，计算一个节点到其他所有节点的最短路径。

该算法的基本思想是，从起点开始，依次计算每个节点到起点的距离，并选择距离最短的节点作为下一个起点，直到所有节点都被考虑过为止。算法的步骤如下：

通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。
此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。
然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。
重复第4步操作，直到遍历完所有顶点