数据结构与应用中的图类型
已发表: 2022-11-25介绍
图是包含节点和边的非线性结构。 它可以包括由连接一对节点的边所持有的一组有限或无限节点。 数据结构是任何编码概念的重要组成部分； 因此，牢牢掌握数据结构中不同类型的图可以帮助您解决复杂的现实世界问题。
在当今世界，数据就是力量。 因此，有效地组织数据以便于访问对任何程序员来说都是必不可少的。 数据结构及其各种图表的知识使您的编码技能能够针对现实世界的问题并有效地提供其解决方案。
学习数据科学以获得超越竞争对手的优势
让我们来看看数据结构中常用的不同类型的图，以及它们在现实生活中的应用。
数据结构中的图类型
数据结构是所有语言的实用数据存储标准，例如python图数据结构或java图数据结构。 掌握所有类型的图应该是任何有志于研究数据结构的人的首要任务。 由于图论在现实生活中有许多应用，因此它们在数据结构中变得至关重要。
数据结构中的各种图类型如下：
1.空图
顾名思义，空图是空的； 换句话说，它是一个没有边的图。 它仅由图中的孤立顶点和空边集组成。
2. 有限图
如果边和节点的数量由图中的有限个数组成，则该图称为有限图。
3.无限图
如果一个图中的节点数和边数不能为有限数，则该图称为无限图。 无限图是不可数的，这意味着您无法计算此类图中节点或边的数量。
4. 简单图
当一对顶点之间只有一条边时，称图是简单图。 因此，图中两个节点由一条边连接，可以确定它们之间的关系。
5.多图
如果一对节点与图中的多条边相连，则该图称为多图。 多图不包含自环。 多图中可以存在两种边。 他们是：
平行边
平行的边，就像从一个源头到同一目的地的两条平行道路，被称为平行边。
环形
这是一条源顶点和目标顶点相同的边。
检查我们的美国 - 数据科学计划
| 数据科学和商业分析专业证书课程 | 数据科学理学硕士 | 数据科学理学硕士 | 数据科学高级证书课程 |
| 数据科学执行 PG 计划 | Python 编程训练营 | 商业决策数据科学专业证书课程 | 数据科学高级课程 |
6.有向图
如果两个节点或顶点之间存在的所有边都具有定义的方向，则称该图是有向的。 有向图也称为有向图。 我们可以通过查看有向图来确定起始和结束节点。 请记住，有向图中的所有边都必须是有向的才能称为有向图。
7. 无向图
如果很难通过查看图的边来识别起始节点和结束节点，则称该图为无向图。 就像有向图一样，边必须是无向的才能称为无向图。
8.连通图
连通图是所有节点之间至少存在一条路径的图。 简单来说，如果您从连通图中的一个节点开始，您应该能够访问图中存在的每个节点。 因此，每个节点至少应该有一条路径。
9.断开连接的图
在这种类型的图中，一对节点或顶点之间不存在边。 因此，与连通图不同，从任何顶点到达所有节点是不可能的。 如果任何一对顶点之间没有路径，则称为不连通图。
10. 完整图
只有当每个节点之间存在边时，图才被认为是完整的，这意味着边将连接图中的所有顶点。 n 个顶点的完整图表示为Kn ，图中的边数为nC2 。
11.循环图
一张图应该至少有一个循环组件才能被认为是循环图。 相反，如果图不包含任何循环，则认为它是无环图。
12.正则图
在正则图中，所有顶点的度数应该相同。 节点的度可以定义为与其相连的节点数。 因此，在规则图中，所有节点都应连接到相同数量的节点。
13.二分图
对于二分图，它应该满足以下条件。
- 该图应分为顶点集。
- 边应该只在一组节点到另一侧之间形成。 此规则防止同一组节点的两个顶点之间的连接。
- 这两个组之间不应有任何公共顶点。
遵循上述所有规则的图应被视为二分图。
14. 标记图
图中的边可以被加权。 与边缘关联的权重可以理解为通过该边缘的成本。 这些值可以基于固定参数并且可以在图形之间改变。 现在，如果所有的边都持有一些与之相关的权重，那么该图可以称为标记图。
15.有向无环图
有向无环图是有向图和无环图的组合，其中图的有向边不形成任何形式的循环。 相反，有向循环图是具有形成循环的有向边的图。
图在数据结构中的应用
图在计算机科学中最突出的应用是计算流的表示。 图的其他一些著名用例是：
1.谷歌地图
在谷歌地图中，图形数据结构定义和计算交通系统。 当一条道路与另一条道路相遇并形成交叉路口时，它被认为是一个节点，而两个这样的节点之间的道路被视为一条边。 因此，谷歌地图使用图形数据结构为您找到到达目的地的最短和最快的方式。
2.脸书
Facebook 使用无向图来识别用户和用户的朋友。 每个用户都被视为顶点，将他们作为朋友加入的连接是网络的边缘。 借助基于图形数据结构的算法，Facebook 会建议“您可能认识的人”并显示“共同的朋友”。
3.万维网
万维网是有向图的一个例子。 这也是谷歌排名系统背后的基本思想。 在万维网系统中，每个网站和网络应用程序都被视为一个节点或顶点，从一个网站到另一个网站的链接被视为边缘。
4. 操作系统
操作系统是资源分配图的一个常用案例，它使用每个进程和资源作为节点或顶点。 边缘出现在资源到分配的进程之间或从请求进程到请求的资源之间。 有时这个循环可能会形成一个无限循环，初始化死锁。
5. 地图系统
您的 GPS 是一种广泛使用的图形案例，可借助该技术定位附近的餐馆、商店和您选择搜索的地点。
6.微软Excel
Microsoft Excel 中使用有向无环图或 DAG。
7. Dijkstra算法
Dijkstra 算法使用图形数据结构来识别两个节点之间的最短路径，或者在某些情况下，识别两个以上节点之间的最短路径。
8. 飞行网络：
计算优化的飞行网络是图数据结构的另一个现实应用。 如果将机场视为节点，将路线视为边，则数据完全符合图表的标准。 这就是为什么在各种增强算法的帮助下，可以确定两个机场或节点之间的最佳路线。
这些是图形在数据结构中的各种应用，在全球范围内用于各种应用程序和系统，以组织和维护它们的平稳运行，
开始你的数据科学家之旅
如果你想成为一名数据科学家并使用我们学到的各种图表巧妙地处理数据，请查看 upGrad 上范围广泛的数据科学课程。 最受欢迎的课程之一是关于数据科学的 PG-IIITB 课程，这是一门适合有抱负和崭露头角的数据科学家入门的优秀课程！
这是课程提供的内容。
- 来自行业专家和导师的 360 度职业支持
- 行业项目的实践经验和详细的案例研究，以衡量常规进展
- 与全球所有部门的数据科学专家建立联系
您还可以查看有关数据科学的所有其他upGrad 课程。