Python 图论

图（Graphs）

图是一种非线性数据结构，由顶点（节点）和边组成。

顶点，也称为节点，是图中的一个点或一个对象，而边用于将两个顶点相互连接。

图是非线性的，因为这种数据结构允许我们通过不同的路径从一个顶点到达另一个顶点，这与数组或链表等线性数据结构不同。

图用于表示和解决数据由对象及其之间的关系组成的问题，例如：

• 社交网络：每个人都是一个顶点，关系（如友谊）是边。算法可以推荐潜在的朋友。
• 地图和导航：地点（如城镇或公交车站）存储为顶点，道路存储为边。当以图的形式存储时，算法可以找到两个地点之间的最短路线。
• 互联网：可以用图来表示，网页作为顶点，超链接作为边。
• 生物学：图可以模拟神经网络或疾病传播等系统。

图的表示方法

图的表示方法告诉我们图在内存中是如何存储的。

不同的图的表示方法可以：

• 占用或多或少的空间。
• 搜索或操作的速度更快或更慢。
• 根据我们拥有的图的类型（加权、有向等）以及我们想要对图做什么，选择更适合的表示方法。
• 比其他方法更容易理解和实现。

以下是不同图的表示方法的简要介绍，但在本教程的后续部分中，我们将使用邻接矩阵作为图的表示方法，因为它易于理解和实现，并且适用于本教程中所有相关情况。

图的表示方法存储有关哪些顶点是相邻的以及顶点之间的边是如何的信息。如果边是有向的或加权的，图的表示方法会略有不同。

如果两个顶点之间有一条边，则它们是相邻的或邻居。

邻接矩阵图表示方法

邻接矩阵是本教程将使用的图的表示方法（结构）。

下一页将展示如何实现邻接矩阵。

邻接矩阵是一个二维数组（矩阵），其中索引 (i,j) 处的每个单元格存储有关从顶点 i 到顶点 j 的边的信息。

下面是一个图及其邻接矩阵表示方法。

上面的邻接矩阵表示一个无向图，因此值 "1" 仅告诉我们边在哪里。此外，邻接矩阵中的值是对称的，因为边是双向的（无向图）。

要使用邻接矩阵创建有向图，我们必须通过在正确的索引 (i,j) 处插入值来决定边的起点和终点。为了表示加权图，我们可以在邻接矩阵中放入除 '1' 以外的其他值。

下面是一个有向加权图及其邻接矩阵表示方法。

在上面的邻接矩阵中，索引 (0,1) 处的值 3 告诉我们存在一条从顶点 A 到顶点 B 的边，且该边的权重为 3。

如你所见，权重直接放入邻接矩阵中对应边的位置，对于有向图，邻接矩阵不必是对称的。

邻接表图表示方法

如果我们有一个具有许多顶点的“稀疏”图，与使用邻接矩阵相比，使用邻接表可以节省空间，因为邻接矩阵会为不存在的边在空数组元素上保留大量内存。

“稀疏”图是指每个顶点仅与图中其他顶点的一小部分有边相连的图。

邻接表有一个包含图中所有顶点的数组，并且每个顶点都有一个链表（或数组），其中包含该顶点的边。

在上面的邻接表中，顶点 A 到 D 被放置在一个数组中，并且数组中的每个顶点旁边都写有其索引。

数组中的每个顶点都有一个指向链表的指针，该链表表示该顶点的边。更具体地说，链表包含相邻（邻居）顶点的索引。

例如，顶点 A 有一个指向链表的链接，该链表包含值 3、1 和 2。这些值是 A 的相邻顶点 D、B 和 C 的索引。

邻接表也可以表示有向加权图，如下所示：

在上面的邻接表中，顶点存储在数组中。每个顶点都有一个指向链表的指针，链表中的边存储为 i,w，其中 i 是边所指向的顶点的索引，w 是该边的权重。

例如，节点 D 有一个指向链表的指针，该链表有一条指向顶点 A 的边。值 0,4 表示顶点 D 有一条指向索引 0（顶点 A）的顶点的边，且该边的权重为 4。