图的实现和表示
图是一种二元关系。它提供了一组强大的可视化功能,即由线(称为边)或箭头(称为弧)连接的点(称为节点)。在这方面,图是树数据模型的一般化。与树一样,图也有几种形式:有向、无向和标记。
有向图与无向图
一个
图表数据类型的最小描述
作为一种抽象类型,我们可以将图视为存储在图的边和节点(节点有时也称为顶点)上的元素的集合。我们需要处理图的基本方法如下: 如前所述,有两种表示图的标准方法:邻接表和邻接矩阵实现。我们将在本节中讨论这些表述。 邻接表实现 使用邻接表实现图的一种常用方法是使用一个以数组作为值的哈希表,或者使用一个以链表作为值的哈希表。由于Python结合了数组和链表的思想,我们可以很容易地实现这种表示,使用一个字典,其中节点作为键,列表作为值。
1 2 3 4 5 6 7
节点
12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
类