DSA 图
图
图是一种非线性数据结构，由顶点（节点）和边组成。
顶点，也称为节点，是图中的一个点或对象，而边用于连接两个顶点。
图是非线性的，因为与数组或链表等线性数据结构不同，图结构允许我们有多条路径从一个顶点到达另一个顶点。
图用于表示和解决数据包含对象及其之间关系的问题，例如：
- 社交网络：每个人是一个顶点，而关系（如友谊）是边。算法可以推荐潜在的朋友。
- 地图和导航：地点，如城镇或公交车站，存储为顶点，道路存储为边。当存储为图时，算法可以找到两个地点之间的最短路径。
- 互联网：可以表示为一个图，网页是顶点，超链接是边。
- 生物学：图可以模拟神经网络或疾病传播等系统。
图的属性
使用下面的动画来了解不同的图属性，以及这些属性如何组合。
加权图是指边具有值的图。边的权重值可以表示距离、容量、时间或概率等。
连通图是指所有顶点都通过边以某种方式连接的图。不连通的图是具有孤立（不相交）子图或单个孤立顶点的图。
有向图，也称为图，是指顶点对之间的边具有方向。边的方向可以表示层次结构或流动。
循环图的定义取决于它是否有向
- 有向循环图是指您可以沿着有向边沿着一条路径前进，该路径形成一个循环。移除动画中从 F 到 G 的有向边，有向图就不再是循环图了。
- 无向循环图是指您可以在不使用同一条边两次的情况下，回到您开始的同一个顶点。上面的无向图是循环的，因为我们可以在不重复使用相同边的情况下，从顶点 C 开始并最终回到顶点 C。
自环，也称为自我循环，是从同一顶点开始并结束于同一顶点的边。自环是仅由一条边组成的循环。通过在动画中顶点 A 添加自环，图就变成了循环图。
图的表示
图的表示告诉我们图是如何存储在内存中的。
不同的图表示可以
- 占用更多或更少的空间。
- 搜索或操作速度更快或更慢。
- 根据我们拥有的图的类型（加权、有向等）以及我们想用图做什么，而更适合。
- 比其他表示更容易理解和实现。
下面是对不同图表示的简要介绍，但在本教程接下来的部分，我们将使用邻接矩阵作为图的表示，因为它易于理解和实现，并且适用于本教程中的所有相关情况。
图的表示存储有关哪些顶点是相邻的以及顶点之间的边是如何连接的信息。如果边是有向的或加权的，图的表示会略有不同。
如果两个顶点之间存在边，则它们是相邻的或邻居。
邻接矩阵图表示
邻接矩阵是我们将在本教程中使用的图表示（结构）。
如何实现邻接矩阵将在下一页展示。
邻接矩阵是一个二维数组（矩阵），其中索引 (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。
