图形数据结构和 Algorithms （例子）
陈莎拉
数据结构中的图是什么？
图是一种非线性数据结构，由顶点和边组成，其中顶点包含信息或数据，边则起到连接一对顶点的作用。
它用于解决现实世界的问题，例如寻找到达目的地的最佳路线以及电信和社交网络的路由。用户被视为图中的节点，而连接用户的边则由导线表示。
如果将边表示为 E，将顶点表示为 V，则图 G 可以写成顶点和边的集合，例如 G（V，E）.
数据结构中的图示例
以下是一个简单的图数据结构示例：
这是一个简单的无向图（图的一种类型）。它的顶点集为：{A, B, C, D, E, F}。两个顶点之间形成一条边。例如，A 和 B 之间有一条边连接。但是，A 和 F 之间没有任何边连接。
数据结构中的图形术语
以下是图数据结构中使用的一些重要术语：
| 术语 | 描述 |
|---|---|
| 顶点 | 每个数据元素都称为顶点或节点。在上图中，A、B、C、D 和 E 都是顶点。 |
| 边缘（弧） | 连接两个节点或顶点的链接称为边（弧）。它有两个端点，表示为（起始顶点，结束顶点）。 |
| 无向边 | 它是双向边。 |
| 有向边 | 它是一条单向边。 |
| 加权边缘 | 带有值的边。 |
| 学位 | 在图中，与一个顶点相连的边的数量称为该顶点的度。 |
| 入度 | 连接到顶点的传入边的总数。 |
| 出度 | 连接到顶点的传出边的总数。 |
| 自循环 | 如果一条边的两个端点重合，则称该边为自环。 |
| 邻接 | 如果两个顶点之间有一条边连接，则称这两个顶点相邻。 |
数据结构中的图类型
以下是最常见的 数据结构中的图类型:
- 有向图
- 无向图
- 加权图
- 双向图
- 无限图
- 空图
- 简单图
- 多图
- 完整图
- 连通图
- 循环图
- 有向无环图（DAG）
- 循环图
- 二分图
- 欧拉图
- 汉密尔顿图
如何在数据结构中表示图？
图通常以两种表示形式之一存储在内存中。选择哪种表示形式会影响图使用的内存量以及常见操作的运行速度。
- 邻接矩阵： 这是一个二维 V × V 数组，其中单元格 [i][j] 为 1（或边的权重）表示顶点 i 和顶点 j 之间存在边，否则为 0。它允许 O(1) 的边查找，但占用 O(V²) 的空间，因此最适合稠密图。
- 邻接表： 一个列表数组，其中每个顶点存储一个与其相邻顶点的列表。它使用 O(V + E) 的空间，并且对于稀疏图非常高效，这就是为什么大多数现实世界的图都使用它的原因。
您可以阅读更多相关内容。 图的邻接表和矩阵表示 教程。
图形数据结构的应用
图有很多应用场景。许多算法都使用图。以下是图的一些应用：
- Google 地图使用图表来查找两条道路的交点并计算两点之间的距离。例如： Dijkstra算法，用于查找起点和终点之间的最短距离。
- Facebook 使用图论来查找用户的共同好友。它的算法将每个用户视为图论中的一个节点。
- 资源分配采用有向无环图（DAG），它会检查资源之间的依赖关系。
- 此 Google 搜索引擎使用图表来创建网站排名。
- 一张地图ping 该设备使用图数据结构。
- A 路由器 其协议使用图来学习到达目的地的路径。
