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)