图论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)
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.souzhinan.com/kj/298999.html