图形数据结构和 Algorithms （例子）
陈莎拉
数据结构中的图是什么？
图是一种由顶点和边组成的非线性数据结构，其中顶点包含信息或数据，边充当顶点对之间的链接。
它用于解决实际问题，例如找到到达目的地的最佳路线以及电信和社交网络的路线。用户被视为图中的节点，而线是连接用户的边。
如果将边表示为 E，将顶点表示为 V，则图 G 可以写成顶点和边的集合，例如 G (V, E)
数据结构中的图示例
以下是图形数据结构的一个简单示例：
这是一个简单的无向图（图的一种）。这里的顶点集是：{A，B，C，D，E，F}。两个顶点创建一条边。例如，A 和 B 有一条边相连。但是，A 和 F 没有与任何边相连。
数据结构中的图形术语
以下是图形数据结构中使用的一些重要术语：
| 按揭年数 | 描述 |
|---|---|
| 顶点 | 所有数据元素都称为顶点或节点。在上图中，A、B、C、D 和 E 是顶点。 |
| 边缘（弧） | 连接两个节点或顶点的链接称为边（弧）。它有两个端点，表示为（startingVertex，endingVertex）。 |
| 无向边 | 它是双向边。 |
| 有向边 | 它是一条单向边。 |
| 加权边缘 | 具有价值的优势。 |
| 学位 | 在图中，连接到一个顶点的边的数量称为度。 |
| 入度 | 连接到顶点的传入边的总数。 |
| 出度 | 连接到顶点的传出边的总数。 |
| 自循环 | 如果一条边的两个端点重合，则称该边为自环。 |
| 邻接 | 如果边相连，则称顶点相邻。 |
数据结构中的图类型
以下是最常见的 数据结构中的图类型:
- 有向图
- 无向图
- 加权图
- 双向图
- 无限图
- 空图
- 简单图
- 多图
- 完整图
- 连通图
- 循环图
- 有向无环图（DAG）
- 循环图
- 二分图
- 欧拉图
- 汉密尔顿图
图形数据结构的应用
图表有很多用例。有很多算法都大量使用图表。以下是图表的一些应用：
- Google 地图使用图表来查找两条道路的交叉点并计算两个地点之间的距离。
例如， Dijkstra算法，用于寻找源位置和目标位置之间的最短距离。 - Facebook 使用 Graphs 来寻找用户的共同好友。其算法将每个用户视为图中的一个节点。
- 对于资源分配，使用 DAG（有向无环图）。它检查资源的依赖关系。
- Google 搜索引擎使用图表来为网站创建排名。
- 映射装置采用图形数据结构。
- 路由器 并且t的协议使用Graph来学习目标路径的路径。
