DSA 图
图
图是一种非线性数据结构，由顶点（节点）和边组成。
顶点，也称为节点，是图中的一个点或对象，边用于连接两个顶点。
图是非线性的，因为这种数据结构允许我们从一个顶点到另一个顶点有多种路径，这与数组或链表等线性数据结构不同。
图用于表示和解决数据包含对象和对象之间关系的问题，例如
- 社交网络：每个人都是一个顶点，关系（如友谊）是边。算法可以建议潜在的朋友。
- 地图和导航：地点，如城镇或公交车站，存储为顶点，道路存储为边。算法可以找到存储为图的两地之间的最短路径。
- 互联网：可以表示为一个图，网页作为顶点，超链接作为边。
- 生物学：图可以模拟神经网络或疾病传播等系统。
图的属性
使用下面的动画来了解不同的图属性，以及如何将这些属性组合起来。
加权 图是指边具有值的图。边的权重值可以表示距离、容量、时间或概率等。
连通 图是指所有顶点都通过边相互连接的图。非连通图是指包含孤立（不连通）子图或单个孤立顶点的图。
有向 图，也称为有向图，是指顶点对之间的边具有方向的图。边的方向可以表示层次结构或流。
循环图的定义取决于它是有向的还是无向的
- 有向循环 图是指可以沿着有向边走出一条圆圈路径的图。从 F 到 G 的有向边从上面的动画中移除，使得有向图不再是循环图。
- 无向循环 图是指可以回到起始顶点，而不使用相同边两次的图。上面的无向图是循环图，因为我们可以从顶点 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。
