数据结构：图基本介绍
应用背景
图表用于不同的行业和领域：
- GPS系统和谷歌地图使用图表来查找从一个目的地到另一个目的地的最短路径。
- 社交网络使用图表来表示用户之间的连接。
- Google搜索算法使用图表来确定搜索结果的相关性。
- 运营研究是一个使用图表来寻找降低运输和交付货物和服务成本的最佳途径的领域。
- 甚至化学使用图表来表示分子！
基本结构
图表用于表示，查找，分析和优化元素（房屋，机场，位置，用户，文章等）之间的连接。下图是图表的示例：
通过上图可以清楚地看到构成图的两个主要元素：连接它们的圆圈和粗线。分别称为图的节点和边。
- 节点：它们是创建网络的元素。它们可以代表房屋，地点，机场，港口，公交车站，建筑物，用户，基本上可以表示连接到网络中其他类似元素的任何东西。
- 边：它们是节点之间的连接。它们可以表示街道，航班，公交路线，社交网络中两个用户之间的连接，或者可能代表您正在使用的上下文中的节点之间的连接的任何内容。
如果两个节点没有通过边连接，则意味着它们之间没有直接连接。但不要惊慌！您可能仍然可以通过一系列边缘从一个节点转到另一个节点，类似于通过几条街道到达您的最终目的地。
例如，在下图中，即使紫色节点（左侧）和黄色节点（右侧）之间没有直接连接（边缘），您也可以从紫色节点到橙色节点，再到粉红色节点，到绿色节点，最后到达黄色节点。
图的基本术语
- |V|=图中顶点（节点）的总数
- |E|=图中的连接总数（边）
在下面的示例中，|V| = 6因为有六个节点（圆圈）,|E| = 7 因为有七个边(线)。
图的类型
- 有向图
在有向图中，边具有方向。它们从一个节点转到另一个节点，并且该方向是单向的。如下图所示，边（连接）现在具有指向特定方向的箭头。 只可以向一个方向前进并到达目的地，无法通过同一条边返回。
- 无向图
在这种类型的图中，边是无向的（它们没有特定的方向）。将无向边视为双向街道。您可以从一个节点转到另一个节点并返回相同的“路径”。在一个图结构中，如果看到图表中的边没有指向特定方向的箭头时，那么该图表是无向的。
- 加权图
在加权图中，每条边都有一个与之相关的值（称为权重）。该值用于表示它们连接的节点之间的某种可量化关系。例如，权重可以表示距离，时间，社交网络中两个用户之间共享的连接数，或者可以用于描述您正在使用的上下文中的节点之间的连接的任何内容。
- 未加权图
相反，未加权的图形不具有与其边缘相关联的权重。可以在社交网络中找到这种类型的图的示例，其中边表示两个用户之间的连接。连接无法量化。因此，边没有重量。
到目前为止，我们的图只有一条边连接每对节点。很自然地询问一对节点之间是否存在多个边缘。 实际上，Multigraphs可以实现这一点！它们可以有多条边连接同一对节点。
- 密集图
密集图表示图中有许多边，那么有多少边才算密集呢？加入有向图中有|V|节点，这意味着每个节点最多可以有|v|连接。因为每个节点都可能与所有其他节点连接并与自身连接。因此，图表可以具有的 最大边数是|V|*|V|，即节点总数乘以每个节点可以具有的最大连接数。当图形中的边数接近最大边数时，图形是密集的。
- 稀疏图
稀疏图形边缘很少。如下图所示，节点之间的连接不多。当图中的边数明显少于最大边数时，图是稀疏的。
- 循环
如果您按照图中的一系列连接边，可能会找到一条路径使得从开始节点出发然后带回到同一节点。这就像“走在圈子里”，就像你在城市周围开车一样，你走的路可以带你回到你的初始位置。在图中，这些“圆形”路径称为“循环”。它们是在同一节点上开始和结束的有效路径。例如，在下图中，您可以看到，如果从任何节点开始，您可以通过跟随边缘返回到同一节点。
循环并不总是“孤立的”，它们是图形的一部分。同时一个图中可能包含多个循环。
图总结
- 图表是Google搜索，Google地图，GPS和社交媒体都有使用的一种数据结构。
- 它们用于表示元素间的连接关系
- 图中的元素称为节点，它们之间的连接称为边。
- 当图形的边具有特定的方向时，可以指向图形，类似于单向街道，或者当它们的边没有特定方向时，类似于双向街道。
- 边可以具有与它们相关联的值，称为权重。
- 如果图形有许多边，则称为密集图。否则，如果边很少，则称为稀疏图。
- 如果多条连接边形成一条允许您返回同一节点的路径，则它们可以形成一个循环。