可视化是简化和解释数据中底层模式的有效方法。每当我处理新数据集时,我做的第一件事都是通过可视化来探索它。这种方法对我来说效果很好。可悲的是，我没有看到很多人使用可视化。这就是为什么我以为我会与世界分享我的一些“秘密酱”！

图的使用就是这样一种可视化技术。它非常有用，可帮助企业做出更好的数据驱动型决策。但要详细了解图的概念，我们必须首先理解它的基础 - 图论。

在本文中，我们将学习图和图论的概念。我们还将查看图的基本原理和基本属性，以及不同类型的图。

然后，我们将通过使用Python应用Graph Theory的概念来研究一个案例，以解决航空业中常见的问题。

目录

1. 图
2. 为什么是图？
3. 图论的起源：柯尼斯堡的七座桥
4. 图的基本原理
5. 与图相关的基本属性和术语
6. 图的类型
7. 继续解决柯尼斯堡的七座桥问题
8. 树状图
9. 图的遍历
10. 实施图论理论解决航空挑战

1. 图表简介

如下图：

这是一个很好的可视化特定项目的商店销售。但这不是图，而是图表。现在您可能想知道为什么这是图表而不是图，对吧？

好吧，图表代表一个函数的图形。让我通过扩展上面的例子来解释这一点。

在特定商品的总单位中，15.1％来自商店A，15.4％来自商店B，依此类推。我们可以用表来表示它：

对应每个商店是他们对整体销售的贡献（％）。在上图中，我们将商店A的贡献率为15.1％，商店B的贡献率为15.4％，依此类推。最后，我们使用饼图将其可视化。但那么这张图表和图之间有什么区别？

要回答这个问题，请考虑以下所示的视觉效果

上述视觉中的点代表权力的游戏，而连接这些点的线代表它们之间的联系。Jon Snow与多个角色有联系，Tyrion，Cersei，Jamie等也是如此。

这就是图的样子：单个点可能与多个点连接，甚至可能与单个点连接。通常，图是顶点（节点）和边的组合。在上面的GOT视觉中，所有字符都是顶点，它们之间的连接是边。

我们现在知道图是什么，但为什么我们首先需要图？我们将在下一节中讨论这个相关问题。

2.为什么是图？

假设您预订了优步出租车。对优步运作至关重要的最重要的事情之一是它能够以有效的方式将驾驶员与车手相匹配。考虑您可以匹配的6种可能的路线。那么，优步如何分配给你？我们可以利用图来描述分配行程的过程如何：

你可以解释，搭乘者可以搭配6种可能的路线（路线1，路线2，......路线6）。以图形式表示这一点使得更容易可视化并最终实现我们的目标，即将最近的路线与用户匹配。上图中的数字表示搭乘者与他/她相应之间的司机的距离（以千米为单位）。我们（当然还有优步）可以清楚地看到Ride 3是最接近的选择。

注意：为简单起见，我只采用距离度量来决定将哪个路线分配给搭乘者。但是在真实生活中的情况下，有多个指标，通过该路线的分配决定，例如搭乘者和司机的等级，不同路线之间的交通状况等。

同样，像Zomato这样的在线食品配送集合商可以选择从相应餐厅接收订单并将其交付给我们的骑手。这是图的众多用例之一，通过它我们可以解决许多挑战。图形使可视化更容易，更易于理解。

为了详细了解图的概念，我们必须首先理解图论。

3.图论的起源：柯尼斯堡的七座桥

我们将首先讨论图论的起源，以便直观地理解图。它的起源背后有一个有趣的故事，我的目标是使用绘图和可视化使其更具吸引力。

这一切都始于柯尼斯堡的七座桥。Königsberg的桥梁面临的挑战（或只是一个脑筋急转弯），只能穿过所有七座桥梁一次穿过城市。让我们首先可视化它，以便清楚地了解问题：

试一试，看看你是否可以通过这种限制来穿越城市。在尝试解决上述问题时，你必须记住两件事（或者我应该说谜语？）：

• 你不能不通过桥梁
• 每个桥梁不得超过一次

您可以尝试任意数量的组合，但它仍然是一个不可能的挑战。每座桥只通过一次的话，人们无法穿过城市。莱昂哈德·欧拉深入研究了这个难题，想出了为什么这是一项不可能完成的任务。让我们分析他是如何做到的：

上图中有四个不同的位置：两个岛屿（B和D），两个大陆（A和C）和七座桥梁。让我们先分别看看每块土地，并尝试找到模式（如果有的话）：

从上面的图像得出的一个推论是每个平台与奇数个桥连接。如果您只希望每个桥跨过一次，那么只有当它连接到偶数桥时才可以进入和离开。换句话说，我们可以概括地说，如果有偶数个桥梁，就有可能离开陆地，而用奇数不可能这样做。

让我们尝试为当前问题添加一座桥，看看它是否可以解决这个问题：

现在我们有2个连接有偶数桥的连接，2个连接有奇数个连接的连接。让我们在添加新桥后绘制一条新路线：

只要再加一座桥就解决了这个问题！您可能想知道桥梁的数量是否在解决此问题中起了重要作用？它应该一直都是吗？嗯，情况并非总是如此。欧拉解释说，随着桥梁的数量，具有奇数个连接桥梁的土地数量也很重要。欧拉将这个问题从陆地和桥梁转换为图形，在那里他将土地表示为顶点，将桥梁表示为边缘：

在这里，可视化简单明了。在我们进一步深入研究这个问题之前，让我们先了解一下图的基本原理和基本属性。

4.图的基本原理

在处理图时，我们应该记住许多关键点和关键词。在本节中，我们将详细讨论所有这些关键字。

• 顶点：这是多条线相交的点。它也被称为  节点。顶点通常用字母表示，如上所示。

• 边缘：它是连接两个顶点的线。

• 图：如上一节所述，图是顶点（节点）和边的组合。G =（V，E）其中V表示所有顶点的集合，E表示图形的所有边缘的集合。

• 顶点度数：顶点的度数是连接到它的边数。在下面的例子中，顶点A的度，deg（A）=顶点B的3Degree，deg（B）= 2

• 平行边：如果两个顶点通过多个边连接，则这些边称为平行边。

• 多图：这些是具有平行边的图：

这些是处理图形时必须牢记的一些基础知识。现在了解图的基本属性。

5.与图相关的基本属性和术语

到目前为止，我们已经看到了图的样子，它有不同的组成部分。现在，我们将把重点转向与图相关的一些基本属性和术语。我们将使用下面给出的图（称为G）并使用相同的术语来理解每个术语：

花点时间考虑以下问题的可能解决方案：

1. 距图表其他顶点的顶点有多远？
2. 顶点和所有其他顶点之间的最大距离是多少？
3. 是否有任何顶点最接近所有其他顶点？如果是这样，最短的距离是多少？
4. 图表的中心点是什么？

我将尝试使用基本图形术语回答所有这些问题：

两个顶点之间的距离：它是两个顶点之间最短路径中的边数。让我们尝试计算顶点A和D之间的距离：

A和D之间的可能路径是：

1.AB - > BC - > CD；

2.AD ；

3.AB - > BD 

在这三条路径中，AD是最短的，只有一条边。因此，A和D之间的距离是1. 

类似地，我们可以计算每对顶点之间的距离。所以，这回答了我们确定任何一对顶点之间距离的第一个问题。

顶点的偏心：它是顶点到所有其他顶点之间距离的最大值。要计算任何顶点的偏心率，我们必须知道该顶点与所有其他顶点之间的距离。让我们计算顶点A的偏心率。因此，距离是：

A和B 之间的距离- 1 

A和C 之间的距离- A

A和D之间的距离 - 1 

所有这些距离的最大值是顶点的偏心率。

A的偏心率，e（A）= 2 

当顶点的偏心率高时，意味着有一些顶点远离该顶点。这回答了我们的第二个问题，我们的目标是计算顶点到所有其他顶点之间的距离的最大值。

连通图的半径：图的所有顶点的最小偏心率称为该图的半径。我们首先要计算每个顶点的偏心率。所有的顶点的偏心率是：

E（A）= 2 

E（B）= 1

E（C） = 2 

e（D）= 1 

所有顶点的偏心率的最小值是该图的半径。在我们的例子中，最小偏心率是1，因此图的半径是：r（G）= 1 

它告诉我们最接近所有其他顶点的顶点的距离。

连接图的直径：图的半径是所有顶点的偏心率的最小值，类似地，图的直径是所有顶点的偏心率的最大值。在我们的例子中，图的直径是：

d（G）= 2

图的中心点：若顶点的偏心率等于该图的半径，则该顶点被称为该图的中心点。图表也可以有多个中心点。在我们的例子中，图的半径是1，偏心率等于1的顶点是B和D.因此'B'和'D'都是图G的中心点。

考虑机场连接图的示例，与大多数其他机场相连的机场可以被视为中央机场。

这些是与图形相关的一些术语。接下来我们将讨论不同类型的图形。

6.图的类型

有各种类型的图表。在本节中，我们将讨论一些最常用的。

空图：这些是不包含任何边的图。

顶点之间没有连接。

非定向图：这些是具有边的图，但这些边没有任何特定的方向。

有向图：当图的边具有特定方向时，它们被称为有向图。

考虑Facebook和Twitter连接的例子。当您将某人添加到Facebook上的朋友列表时，您也将被添加到他们的朋友列表中。这是双向关系，连接图将是非定向关系。如果您在Twitter上关注某个人，那么该人可能不会关注您。这是一个有向图。

连通图：当没有无法到达的顶点时，即每对顶点之间存在一条路径，这种图形称为连通图形。

断开连接的图形：这些是具有无法到达的顶点的图形，即每对顶点之间不存在路径。

如果连接了图形，则始终存在从每个顶点到该图形的所有其他顶点的路径。如果图形断开连接，则始终至少有一个顶点不会与图形的所有其他顶点建立连接。这可以帮助航空公司决定是否所有机场都已连接。他们可以看到连接，如果有任何未连接的机场，可以引入新航班以改善现有情况。

正则图：当图中的所有顶点具有相同的度数时，这些图称为k-正则图（其中k是任何顶点的度数）。考虑下面显示的两个图：

对于Graph-1，每个顶点的度数为2，因此Graph-1是常规图。图-2不是规则图，因为每个顶点的度数不相同（A和D的度数是3，而B和D是2）。

现在我们已经了解了不同类型的图形，它们的组成部分以及一些与图形相关的基本术语，让我们回到我们试图解决的问题，即柯尼斯堡的七座桥。我们将更详细地探讨莱昂哈德·欧拉如何接近并解释他的推理。

 

7.继续看看柯尼斯堡七桥的问题

我们之前看到Euler使用图形转换了这个问题：

这里，A，B，C和D代表陆地，连接它们的线是桥。我们可以计算每个顶点的程度。

deg（B）= 5

deg（A）= deg（C）= deg（D）= 3

欧拉表明，使用每个边（桥）只走一次图（城市）的可能性，严格依赖于顶点（陆地）的度数。并且这样的路径仅包含图形的每个边缘，称为欧拉路径。

你能算出欧拉的问题路径吗？我们试试吧！

这就是使用图形和欧拉的路径来解决经典的柯林斯堡七桥问题。这基本上是图论的起源。感谢Leonhard Euler！

8.树状图简介

树状图是表示图形的最有效和最有效的方法之一。在本节中，我们将了解二叉搜索树是什么，它们如何工作，以及它们如何使可视化更易于解释。但在此之前，花点时间了解树状图究竟是什么。

树状图是甚至不包含单个循环的图：

在上面的例子中，第一个图没有循环（也就是树状），而第二个图有一个循环（ABECA，因此它不是树状）。

树的元素称为节点。（A，B，C，D和E）是上述树中的节点。树的第一个节点（或最顶层节点）称为根节点，而最后一个节点（上例中的节点C，D和E）称为叶节点。所有剩余的节点都称为子节点（在我们的例子中是节点B）。

现在是时候进入图论的一个最重要的主题，即图的遍历。

9.图的遍历（Graph Traversal）

假设我们想要在图中标识特定节点的位置。我可以用什么方法来识别图的节点？怎么开始？哪个应该是起点？一旦我们知道起点，如何进一步前进？我将通过解释图的遍历的概念来尝试回答本节中的所有这些问题。

图遍历是指以明确定义的顺序访问图形的每个顶点和边缘一次。因为遍历的目的是仅访问每个顶点一次，所以我们保持覆盖顶点的轨迹，这样我们就不会覆盖相同的顶点两次。图遍历有各种方法，我们将讨论一些着名的方法：

广度优先搜索

我们从源节点（根节点）开始并逐层遍历图。广度优先搜索的步骤是：

• 首先水平移动并访问当前图层的所有节点。
• 移至下一层并重复上述步骤。

让我用可视化来解释它：

因此，在广度优先搜索中，我们从源节点（在我们的例子中是A）开始，然后向下移动到第一层，即第1层。我们通过水平移动（B - > C）覆盖该层中的所有节点。然后我们转到下一层，即第2层并重复相同的步骤（我们从D - > E - > F移动）。我们继续此步骤，直到覆盖所有图层和顶点。

这种方法的主要优点是我们总能找到达到目标的最短路径。这适用于小图和树，但对于更复杂和更大的图，它的性能非常慢，并且还需要大量内存。我们将研究另一种遍历方法，与BFS相比，它占用更少的内存空间。

深度优先搜索

我们先来看看这种方法涉及的步骤：

• 我们首先选择源节点并存储其所有相邻节点。
• 然后，我们从存储的节点中获取节点并存储其所有相邻节点。
• 重复此过程，直到没有节点可用。

深度优先搜索以上示例的顺序为：

A - > B - > D - > E - > C - > F.

一旦路径被完全探索，它就可以从内存中删除，因此DFS只需要存储根节点，根节点的所有子节点以及它当前的位置。因此，它克服了BFS的内存问题。

二叉搜索树

在该方法中，树的所有节点按排序顺序排列。让我们看一下二进制搜索树的示例：

如前所述，上述树中的所有节点都是根据条件排列的。假设我们想要访问值为45的节点。如果我们要遵循BFS或DFS，我们需要大量的计算时间才能达到它。现在让我们看看二进制搜索树如何帮助我们使用最少的步骤访问所需的节点。使用二进制搜索树到达值为45的节点的步骤：

• 我们从根节点开始，即50。
• 现在45小于50（45 <50），所以我们移动到根节点的左边。
• 然后我们比较这些值。事实证明45大于40（45> 40），所以我们移动到该节点的右侧。
• 这里我们处于值为45的节点。

这种方法非常快，并且内存也非常少。图论的大多数概念都已被涵盖。接下来，我们将尝试实现这些概念，以使用Python解决实际问题。

10.用Python实现图论以解决航空挑战

最后，我们开始使用Python中的数据！在这个数据集中，我们记录了来自美国的700多万个航班。提供了以下变量：

• 出发地和目的地
• 预定的抵达和离开时间
• 实际抵达和离开时间
• 旅程日期
• 出发地和目的地之间的距离
• 航班的总飞行时间

这是一个巨大的数据集，我从这篇文章中只拿了一个样本。我们的想法是让您了解使用此样本数据集的概念，然后您可以将它们应用于整个数据集。从这里下载我们将用于案例研究的数据集。我们将首先导入常用的库，并读取以.csv格式提供的数据集：

import pandas as pd
import numpy as np
data = pd.read_csv('data.csv')

让我们看一下使用head（）函数的数据集的前几行：

data.head（）

这里，CRSDepTime，CRSArrTime，DepTime和ArrTime分别代表预定的出发时间，预定的到达时间，实际出发时间和实际到达时间。Origin和Dest表示旅程的出发地和目的地。

从一个机场到另一个机场通常可以有多条路径，目的是找到所有机场之间最短的路径。我们可以通过两种方式将路径定义为最短路径：

• 按距离
• 按飞行时间

我们可以使用迄今为止学到的图论的概念来解决这些问题。你能回忆起制作图表需要做些什么吗？

答案是识别顶点和边缘！我们可以通过将所有机场表示为顶点以及它们之间的路径作为边来将问题转换为图形。我们将使用NetworkX来创建和可视化图形。NetworkX是一个Python包，用于创建，操作和研究复杂网络的结构，动态和功能。您可以在此处参阅NetworkX的文档。

安装NetworkX后，我们将使用数据集为图形创建边和顶点：

import networkx as nx
df = nx.from_pandas_edgelist(data, source='Origin', target='Dest', edge_attr=True)

它将自动存储顶点和边。快速浏览一下我们创建的图形的边和顶点：

df.nodes（）

df.edges（）

让我们使用networkx的matplotlib和draw_networkx（）函数绘制和可视化图形  。

import matplotlib.pyplot as plt
% matplotlib inline

plt.figure(figsize=(12,8))
nx.draw_networkx(df, with_labels=True)

上述惊人的可视化代表了不同的飞行路线。假设乘客想要从AMA到PBI采取最短路线。图论可以帮你解决！

让我们尝试根据机场AMA和PBI之间的飞行时间来计算最短路径。我们将使用Dijkstra的最短路径算法。该算法找到从源顶点到给定图的所有顶点的最短路径。让我简要介绍一下该算法遵循的步骤：

1. 创建一个sptSet（最短路径树集），它跟踪最短路径树中包含的顶点，即计算并最终确定与源顶点的最小距离。最初，此设置为空。
2. 为输入图中的所有顶点指定距离值。我们为源顶点指定值0，为所有剩余顶点指定INFINITE值。
3. 直到sptSet不包含所有顶点，我们遵循以下子步骤：

• 选择一个不在sptSet中并且最接近源顶点的顶点
• 在sptSet中包含该顶点
• 更新所有相邻顶点的距离

让我们举一个例子来更好地理解这个算法：

这里的源顶点是A.数字表示顶点之间的距离。最初，sptSet为空，因此我们将为所有顶点指定距离。距离是：

{0，INF，INF，INF，INF，INF}，其中INF代表INFINITE。

现在，我们将选择具有最小距离的顶点，即A，它将包含在sptSet中。所以，新的sptSet是{A}。下一步是选择一个不在sptSet中并且最接近源顶点的顶点。在我们的例子中，这是B，距离值为2.所以这将被添加到sptSet。

sptSet = {A，B}

现在我们将更新与顶点B相邻的顶点的距离：

 

顶点F的距离值变为6.我们将再次选择具有最小距离值的顶点，该距离值尚未包括在SPT中（距离值为4的C）。

sptSet = {A，B，C}

我们将遵循类似的步骤，直到sptSet中包含所有顶点。让我们实现这个算法，并尝试计算机场之间的最短距离。我们将使用networkx 的  dijkstra_path（）函数来执行此操作：

shortest_path_distance = nx.dijkstra_path（df，source ='AMA'，target ='PBI'，weight ='Distance'）
Shortest_path_distance

这是两个机场之间根据它们之间的距离尽可能短的路径。我们还可以通过改变超参数权重='AirTime'来计算基于飞行时间的最短路径：

shortest_path_airtime = nx.dijkstra_path（df，source ='AMA'，target ='PBI'，weight ='AirTime'）
shortest_path_airtime

这是基于飞行时间的最短路径。直观且易于理解，这完全是关于图论的！

小结

这只是图论的众多应用之一。我们可以将它应用于几乎任何类型的问题，并获得解决方案和可视化。我能想到的图论的一些应用是：

• 找到发布帖子的最佳途径
• 代表通信网络。例如，可以使用有向图来表示网站的链接结构。
• 使用他们的社交连接图确定一个人的社交行为
• 航空公司案例研究中讨论的旅行计划

参考链接：https://www.analyticsvidhya.com/blog/2018/09/introduction-graph-theory-applications-python/