图论101

The City of Königsberg, Historic Cities Research Project

图论是数学的一个非常广泛的分支，非常适用于现实世界中的问题。 最初，图论是"发明"来解决现实问题的，此后，它像所有其他数学分支一样，被抽象数学家所劫持。

在本教程和后续教程中，我们将介绍一些图论算法及其在Python中的实现。 现在，回到主题。

什么是图？

简而言之，图是一组顶点/节点和边。 如果您对" set"不满意，请用collection代替。

A simple graph showing connections among people. Image From William Fiset

什么是顶点/节点？

在上图中，顶点/节点将是人物。

顶点是图的基本单位。 它几乎可以代表任何实体，通常以圆圈表示。

什么是边？

在上图中，连接人的线是边。

顶点之间的线或连接称为边。 它可以表示顶点之间的任何类型的关系。

图的类型

有向图

边上具有方向的图称为有向图。 它可以用来显示与前辈（从父母到孩子的箭头）或祖先（从孩子到父母的箭头）的关系。

A Directed Graph. Image From William Fiset

无向图

边上没有方向的边的图称为无向图。 它可用于显示双向道路。

A Un-Directed Graph. Image From William Fiset

加权图

边上带有数字的图形，代表交易成本，旅途公平，城市之间的距离等。它可以具有任何类型的边。

A Weighted Graph. Image From William Fiset

树

没有循环的无向图是一棵树。 在这里，循环意味着只有一种方法可以通过跟随给定其他节点的边缘来到达节点。

一棵树的所有节点都通过一条边连接到其他某个节点，并且有N个节点的N-1个边。

Trees. Image From William Fiset

表示图

A Graph Example. Image From William Fiset

表示图形的方法有很多，最常见的两种是：

邻接矩阵

假设图中有N个节点。 我们可以使用具有N行和N列的矩阵来表示它，其中该矩阵的行和列将代表一个节点，并且其中的条目代表有向边（有或没有权重）。

它们形成代表行的节点到代表列的节点。 通常，0或无穷大用于表示节点之间没有边缘。 在Python中，邻接矩阵可以表示为：

idxMap = {"A":0, "B":1, "C":2, "D":3}
adjacencyMatrix=[
[0, 4, 1, 9], # A
[3, 0, 6, 11], # B
[4, 1, 0, 2], # C
[6, 5, -4, 0] # D
]
#A B C D

邻接表

类似地，对于N个节点的图，我们可以使用邻接表来表示该图，其中节点的所有边都保留在元组列表（节点，权重）中。 在python中，它可以表示为：

idxMap = {"A":0, "B":1, "C":2, "D":3}
adjacencyMatrix=[
[0, 4, 1, 9], # A
[3, 0, 6, 11], # B
[4, 1, 0, 2], # C
[6, 5, -4, 0] # D
]
#A B C D

嵌套字典

我使用嵌套字典（这就是我所说的）和带集合的字典（如果节点没有权重的边）来表示图。

Graph = {
"A", {"B":4,"C":1},
"B", {"C":6},
"C", {"A":4,"B":1, "D":2},
"D", {},
}

在下一篇文章中，我将使用不同的方法发布精心设计的图类的Python代码，我们将使用该代码来实现图算法。

(本文翻译自sleepingFish的文章《Graph Theory Algorithms "Simplified"》，参考：
https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222)

免责声明：本文来自闻数起舞客户端，不代表超天才网的观点和立场。文章及图片来源网络，版权归作者所有，如有投诉请联系删除。