数据结构:图基本介绍

创业故事 阅读(1691)

  喜欢就点关注吧!

  应用背景

不同行业和行业的图表:

GPS系统和谷歌地图使用图表来查找从一个目的地到另一个目的地的最短路径。

社交网络使用图表来表示用户之间的连接。

Google搜索算法使用图表来确定搜索结果的相关性。

运营研究是一个使用图表来寻找降低运输和交付货物和服务成本的最佳方法的领域。

甚至化学也使用图表来表示分子!

基本结构

图表用于表示,查找,分析和优化元素(房屋,机场,位置,用户,文章等)之间的连接。下图是图表的示例:

从上图中,您可以清楚地看到构成图形的两个主要元素:连接它们的圆圈和粗线。它们分别称为图的节点和边。

节点:它们是创建网络的元素。它们可以代表房屋,地点,机场,港口,公交车站,建筑物,用户,以及基本上可以连接到网络中其他类似元素的任何东西。

边缘:它们是节点之间的连接。它们可以表示街道,航班,公交路线,社交网络中两个用户之间的连接,或者可能代表您正在使用的上下文中的节点之间的连接的任何内容。

街道到达你的最终目的地。

例如,在下图中,即使紫色节点(左侧)和黄色节点(右侧)之间没有直接连接(边缘),您也可以从紫色节点到橙色节点,再到粉红色节点,到绿色节点,最后到达黄色节点。

图表的基本术语

| V |=图中的顶点(节点)总数

| E |=图表中的连接总数(边缘)

在下面的示例中,| V |=6因为有六个节点(圆圈),| E |=7因为有七个边(线)。

图表类型

有向图

在有向图中,边缘具有方向。它们从一个节点移动到另一个节点,方向是单向的。如下图所示,边缘(连接)现在有一个指向特定方向的箭头。回去。

无向图

在这种类型的图形中,边缘是无向的(它们没有特定的方向)。将无向边处理为双向街道。您可以从一个节点转到另一个节点并返回相同的“路径”。在图形结构中,如果您看到图形中的边缘没有指向特定方向的箭头,则图形是无向的。

加权图

边缘具有与之关联的值(称为权重)。该值用于表示它们所连接的节点之间的某些可量化关系。例如,权重可以表示距离,时间,社交网络中两个用户之间共享的连接数,或者可以用于描述您正在使用的上下文中的节点之间的连接的任何内容。

未加权的图表

相反,未加权的图形不具有与其边缘相关联的权重。可以在社交网络中找到这种类型的图的示例,其中边缘表示两个用户之间的连接。连接无法量化。因此,侧面没有重量。

边。并排连接同一对节点。

密集的地图

密集的地图显示图中有许多边,所以有多少边被认为是密集的?添加| V |有向图中的节点意味着每个节点最多可以有| v |连接。因为每个节点都可以连接到所有其他节点并连接到自身。因此,图表可以具有的最大边数是| V | * | V |,这是节点的总数乘以每个节点可以具有的最大连接数。当图形中的边数接近最大边数时,图形是密集的。

稀疏图

稀疏图形边缘很少。如下图所示,节点之间的连接不多。当图中的边数明显小于最大边数时。图片很稀疏。

路径由起始节点构成,然后返回到同一节点。这就像“走在一个圆圈里”,就像在城市周围开车一样,你走的路可以带你回到你的初始位置。在图中,这些“循环”路径称为“循环”。它们是在同一节点上开始和结束的有效路径。例如,在下图中,您可以看到,如果从任何节点开始,则可以通过跟随边缘返回到同一节点。

循环并不总是“隔离”,它们是图形的一部分。同时,图形可能包含多个循环。

地图摘要

图表是Google搜索,Google地图,GPS和社交媒体使用的一种数据结构。

它们用于表示元素之间的连接

图中的元素称为节点,它们之间的连接称为边。

当图形的边缘具有特定方向时,它们可以指向图形,类似于单行道,或者当它们的边缘没有特定方向时,类似于双向街道。

边缘可以具有与它们相关联的值,称为权重。

如果图形有许多边,则称为密集图。否则,如果边缘很少,则称为稀疏图。

允许您返回到同一节点的路径,然后它们可以形成循环。

参考