本节书摘来自异步社区《Python算法教程》一书中的第2章，第2.3节，作者[挪威]Magnus Lie Hetland（赫特兰）， 凌杰 译，更多章节内容可以访问云栖社区“异步社区”公众号查看。
2.3 图与树的实现
在第1章中，我们所举的第一个例子与瑞典及中国境内的导航有关，这是个非常典型的问题。而要诠释这类问题，我们就需要用到算法学中最强大的框架之一——图结构（graph）。其实在许多情况下，如果我们可以将自己的工作诠释成一个图问题的话，那么该问题至少已经接近解决方案了。而如果我们的问题实例可以用树结构（tree）来诠释的话，那么我们基本上已经拥有了一个真正有效的解决方案。
图结构可以用来表现似乎所有类型的结构与系统，从交通网络到通信网络，从细胞核之间的蛋白质交换到人际之间的线上交互等。我们可以通过添加权重值、距离值等额外数据来增强其表现能力，使其能尽可能多地代表不同的问题，如下棋游戏，或根据一组人各自的能力分配工作等。而树结构则只是图的一种特殊情况，所以其大部分针对图的算法和表现形式也适用于树。然而，由于该结构自身的特殊性（它的连接点之间不存在环路），存在一些专用的（简单）算法与表现形式也是可能的。有很多实用的结构形式，如XML文档或者目录层次结构等，实际上也都是用树结构来表现的1——这也说明所谓的“特殊情况”实际上还是相当普遍的。
如果您对图这个术语名词的记忆有些生疏了（或如果这对您来说完全是新的概念的话），可以参考附录C中的“图术语”部分，其要点主要包括。
- 图G = (V , E )通常由一组节点V 及节点间的边E 共同组成。如果这些边是带有方向的，我们就称其为有向图。
- 节点之间是通过边来实现彼此相连的。而这些边其实就是节点v 与其邻居之间的关系。与节点v 相邻的节点，称为节点v 的邻居。一个节点的度数就是连接其边的个数。
- G = (V , E )的子图结构将由V 的子集与E 的子集共同组成。在G 中，每一条路径（path）是一个子图结构，它们本质上都是一些由多个节点串联而成的边线序列（当然，这些节点是不重复的）。环路（cycle）的定义与路径基本相同，只不过它最后一条边所连接的末节点同时是它的首节点。
- 如果我们将图G 中的每条边与某种权值联系在一起，G 就成了一种加权图。在加权图中，一条路径或环路的长度等于各条边上的权值之和；而对于非加权图而言，就直接等于该图的边数了。
- 森林（forest）可以被认为是一个无环路图，而这样的连通图就是一棵树。换句话说，森林就是由一棵或多棵树构成的。
到目前为止，我们只是在用图术语来描述问题，如果想要实现某种解决方案，我们就必须学会用某种数据结构来表示图。事实上，即便您只是想设计一个算法，这也是需要的，因为我们必须了解不同操作在图这种表现形式中的运行时间。其实在某些情况下，图早就在我们的代码或数据中存在了，不再需要其他独立的数据结构。举例来说，如果您要写一个Web爬虫程序，以便自动收集某Web站点中的链接，这时候Web本身就是一个图。再如，您有一个Person类，而该类的friends属性是一个由其他Person类实例组成的list。那么该对象模型本身就是一个图，我们可以在上面运行各种图算法。但是，这些都是实现图的具体方式。
用抽象术语来说，我们通常会倾向于采用一种被称为邻近函数N (v )（neighborhood function）的实现方式。因而，这里往往会涉及一个容器N[v]（或许在某些情况下，它可能只是一个迭代器对象），主要用于存储v的邻近节点。在这个话题上，我们将会与其他许多同类书籍一样，把焦点主要放在邻接列表与邻接矩阵这两种著名的表现形式上，因为它们的可用性和普及率都很高。至于其他替代形式，读者可以参考本章后面“多种表现形式”一节中的相关讨论。
2.3.1 邻接列表及其类似结构
对于图结构的实现来说，最直观的方式之一就是使用邻接列表。基本上就是要针对每个节点设置一个邻居列表（也可以是set等其他容器或迭代器类型）。下面我们来实现一个最简单的：假设现在我们有n 个节点，编号分别为0, …, n-1。
请注意：
节点当然可以是任何对象，可以被赋予任何标签或名称。但使用0, …, n-1区间内的整数来实现的话，会简单许多，因为如果能用数字来代表节点，我们索引起来显然要方便许多。
然后，每个邻接（邻居）列表就都只是一个数字列表，我们可以将它们编入一个大小为n 的主列表，并用节点编号对其进行索引。由于这些列表内的顺序是任意的，所以实际上我们是使用列表来实现邻接集（adjacency sets）。这里之所以使用列表这个术语，主要还是因为传统。值得庆幸的是，Python本身就提供有独立的set类型，这在很多情况下是一个更自然的选择。
下面以图2-3为例，具体说明一下图结构的各种表示法。
提示：
参见本章后面的专栏内容“图结构库（Graph Libraries）”来找到帮助您可视化图结构的工具。
首先，假设我们已经完成了节点的编号工作（a = 0, b = 1, …）。该图可以先用一种简单明了的方式来表示，如清单2-1所示。为了方便起见，我们将节点编号赋值给了一些变量，而这些变量的名称与示例图中的各节点标签相同。当然，您也可以用纯编号形式来完成相关工作。在这里，每个邻接列表旁边都注释了它所属的节点。如果您愿意的话，可以花一两分钟时间确认一下它们在示例图中的对应关系。
清单2-1 简单明了的邻接集表示法
请注意：
在Python 2.7（或3.0）之前的版本中，set类型的字面写法应该是set([1, 2, 3])而非{1, 2, 3}。但如今，空set写法依然是set()，因为{}表示的是空dict。
名词N 在这段代码中的作用就相当于我们之前所讨论的N 函数。在图论中，N (v )代表的是v 的邻居节点集。同样，目前在我们的代码中，N [v ]就是一个v 邻居节点集。假设我们稍早前已经在交互解释器中定义了N ，那么现在就可以随意演练以下图操作了：
提示：
如果某些代码（例如清单2-1中的图定义）存在于某个源文件中，而我们又想跟之前一样，将其引入交互解释器中来研究的话，就得使用Python的-i开关来运行它，像这样：
这样一来，源文件就会在运行之后继续驻留在交互解释器中，以便我们可以在自己的实验中继续使用其中任何可用的全局定义。
在某些情况下，或许另一种表示法的开销会更小一些，即用真正的邻接列表来代替上面的邻接集，具体见清单2-2。在现在这种情况下，其可用操作依然相同，但成员检测却变成了Θ(n )级操作。当然，这也确实是一种明显的速度放缓，但这充其量也仅仅是您需要考虑的（如果真的必要要的话）一个问题而已。（但如果您的所有算法所做的都是其邻居节点的遍历，那使用set对象就不仅毫无意义，而且其开销也会成为实际上不利于我们实现的常数因子。）
清单2-2 邻接列表
这种表示法可能存在着一个争议，即它实际上是一组邻接数组的集合，而并非传统意义上的邻接列表。这是因为在Python中，list类型的背后实际上是一个动态数组（请参考之前关于list的黑盒子专栏中的相关内容）。如果愿意的话，我们也可以实现一个链表类型，并用它来取代Python中的list类型。这类实现允许我们以较低的（渐近）成本对各列表中的任意一点执行插入操作，但这种操作或许并不是我们所需要的，因为新增的邻居节点往往只需简单添加在列表末端就行了。使用list实现的优势主要体现在它是一个已经被调试好了的、速度非常快的数据结构，相较于任何一个您可以用纯Python环境实现的列表结构而言。
当我们执行与图相关的工作时，需要反复遵从一个主题思想，即一个图的最佳表示方法应该取决于我们要用它来做什么。例如，邻接列表（或数组）可以让我们在维持低成本的情况下，对N (v )中所有节点v 进行有效遍历。然而，其在检查u 和v 是否互为邻居时的成本就是Θ(N (v ))了，这时如果该图的结构很密集（如果它的边很多）的话，很可能就会带来一些问题。在这种情况下，邻接集或许是个更好的选择。
提示：
我们也注意到，要想删除一个位于Python list中间的对象，操作成本往往很高，而从list尾端删除就只需要常数时间。所以，如果不在乎邻居节点顺序的话，我们也可以用当前邻接列表中最后一项覆盖掉需要删除的邻居节点（只需要常数时间），然后调用pop方法。
除此之外，我们还可以对这种表示法做一些轻微的变动。我们可以用有序列表来表示这些邻居集。在列表本身不修改的情况下，我们可以让其成员保持有序状态，并用二分法来进行成员检测（相关内容请参考第6章中的黑盒子专栏之二分法）。这样做或许可以在某些方面（主要是内存使用和迭代时间）稍许降低一些成本，但这也导致了其成员检测成为一个复杂度为Θ(lg k )的操作，k 在这里表示的是给定节点的邻居数量。（但这个复杂度还是算相当低的了，当然在实践中，使用内置的set类型还能免去我们不少额外的麻烦。）
除此之外，这种表达还有另一种微调方式，就是用dict类型来替代这里的set或list。在dict类型中，每个邻居节点都会有一个键和一个额外的值，用于表示与其邻居节点（或出边）之间的关联性，如边的权重。其实现起来如清单2-3所示（为任意边附加权重值）。
清单2-3 加权邻接字典
邻接字典版本可以被用来实现一些其他方面的，类似于添加相关权值这样的功能：
当然，只要您愿意，即便是在用不到加权边或类似功能的情况下，也是可以使用邻接字典的（相关值或许可以用None及其他占位符来替代）。这样做不仅能发挥出邻接集合的主要优势，而且（非常非常）适用于尚未提供set类型的旧版Python环境。2
到目前为止，我们用来容纳邻接结构（可能是list、set或dict）的主容器其实都属于列表类型，它们都以节点编号为索引值。当然就灵活性而言，使用dict类型来充当主要结构3会是一种更好的选择（因为它允许我们使用任意可散列的对象来充当节点标签）。用dict容纳邻接集的具体情况如清单2-4所示。需要注意的是，这里是用字符来表示相关节点的。
清单2-4 邻接集的字典表示法
请注意：
如果您在清单2-4中省略了set构造器，最终得到的将是一个邻接字符串，其工作方式相当于一个（不可变的）字符类的邻接列表（其成本会略低一些）。这种表达看上去似乎很无聊，但正如我之前所说，其作用取决于程序的其他部分。例如相关图的数据将从哪里获取？是否已经是以文本的形式？又将如何被使用？
2.3.2 邻接矩阵
图的另一种常见表示法就是邻接矩阵了。这种表示的主要不同之处在于，它不再列出每个节点的所有邻居节点，而是会将每个节点可能的邻居位置排成一行（也就是一个数组，用于对应图中每一个节点），然后用某种值（如True或False）来表示相关节点是否为当前节点的邻居。与之前一样，其最简单的形式也可以用嵌套list来实现，具体如清单2-5所示。同样要提醒的是，节点编号依然是从0到V-1。并且为了让矩阵具有更好的可读性，我们将会用1和0来充当所谓的真值（您也可以用True和False）。
清单2-5 用嵌套list实现的邻接矩阵
其在使用方式上也与邻接列表或邻接集略有不同，这里要检查的不是b是否在N[a]中，而是要检查矩阵单元Na是否为真。同样，我们也不能再用len(N[a])来获取相关节点的邻居数，因为在这里，所有行的长度是相等的，我们得改用sum函数：
在邻接矩阵中，有一些实用的特性是非常值得我们去加以了解的。首先，只要我们不允许出现自循环状态（我们在工作中不会遇到伪图结构），其对角线上的值应该全为假。而且，我们通常会通过向现有表示法中加入双向边元素的方式来实现一个无向图。这也就意味着无向图的邻接矩阵应该是一个对称矩阵。
将邻接矩阵扩展成允许对边进行加权处理，也非常简单：在原来的存储真值的地方直接存储相关的权值即可。例如，对于边（u ,v ）来说，我们只需要将N u 处的True替换成w (u ,v )即可。出于某些实践因素的考虑，我们通常会将一些实际不存在的边的权值设置为无穷大。（这可以确保它们不会被纳入考虑范围，也就是说，在考虑最短路径时，我们只能根据实际存在的那些边来寻找合适路径）虽然其在无穷大的具体表示方式上并没有明确规定，但我们手里确实有一些选项。
一种可能的选项就是使用一个非法的权值，如None、-1（在已知所有权值都为非负数的情况下）。但或许在多数情况下，更实用的做法是设置一个非常大的值。通常对于整型加权值来说，我们用sys.maxint就可以了，尽管事实上谁也无法保证该值确实为这里可能的最大值（毕竟long int类型可能会更大一些）。然而在对浮点型的设计中，倒确实有一个可以代表无穷大的值：inf。虽然该值在Python中没有直接可用的名称，但我们可以通过float('inf')表达式来获取它。4
在清单2-6中，我们示范了如何用嵌套list来实现一个加权矩阵。它的加权情况看起来与清单2-3中的情况基本相同，即inf = float('inf')。此外要注意的是，该矩阵对角线上的值依旧应该全为0，因为即使在没有自循环存在的情况下，相关权值也往往会被解释成某种距离形式。而从习惯上来说，任一节点到自身的距离都应该始终为0。
清单2-6 对不存在的边赋予无限大权值的加权矩阵
当然，尽管加权矩阵可以使相关加权边的访问变得更容易，但目前如成员检测、查找某个特定节点的度（degree），或者乃至于在对邻居的遍历操作上都存在着一些不同之处。也就是说，我们需要对相关的无穷大值进行检测，例如：
请注意，在对度值求和时务必要记得从中减1，因为我们不想把对角线也计算在内。尽管这个表达结构在度值计算上的操作复杂度是Θ(n )，但它很适合于相关成员与度值的查找操作，并且这些操作都能很轻易地在常数时间内完成。此外需要始终记住一点：我们应该根据图的具体用处来选择相关的表示法。
2.3.3 树的实现
在一般情况下，但凡可以用来表示图的方法通常都可以用来表示树，因为树本身就是图的一种特殊情况。然而，树本身也在算法学中扮演着非常重要的角色，并且有许多特定问题是推荐用树结构来解决的。其中大部分树算法（甚至包括第6章中将要讨论的搜索树）都可以被理解成一般图概念中的思路，但特定的树结构会使得它们更容易实现。
其中最容易表示的就是带根的树结构，这种树的每条边都从根出发，并向下方延伸。此类结构所代表的往往是某个数据集所拥有的层次结构，其根节点代表着全部对象（这些对象或许就被直接包含在叶节点内），而其内部各节点所代表的对象都是以该节点为根的树结构的叶节点。在这里，我们甚至可以直接利用类似直觉，将其各个子树组织成一个子树列表。下面，我们来看一个简单的树结构（见图2-4）。
我们可以将该树表示成一个二维列表（lists of lists），具体如下：
在这种方法中，每个列表表示的都是相应内部（匿名）节点所拥有的一个包含其所有相邻节点（也叫“子节点”）的列表。在第二个示例中，我们所访问的依次是根节点的第三个子节点，然后是该子节点的第二个子节点，最后是这个节点的第一个子节点（见图中所突显的路径）。
在某些情况下，由于我们可以事先知道其内部节点下所能拥有的最大子节点数（例如，在二叉树中，各节点最多只能拥有两个子节点），所以可以选择其他表示法，如为各对象的各子节点设置相应的属性，具体如清单2-7所示。
清单2-7 二叉树类
这样一来，我们就可以像下面这样使用这个Tree类了：
再如，我们还可以用None值来表示不存在的子节点（例如当某节点只有一个子节点时）。当然，您可以根据自己所要表述的核心内容来自由搭配这些技术（例如，在各节点实例中选择子节点列表或是子节点集合）。
而对于那些没有内置list类型的语言，我们还有另一种常见的树实现方式，即采取“先子节点，后兄弟节点”的表示法。在这种表示法里，每一个树节点都有两个用于引用其他节点的“指针”或属性，这似乎与二叉树的情况很类似。然而在这里，第一个引用指向的是当前节点的第一个子节点，而第二个引用所指向的则是其下一个兄弟节点（顾名思义）。换句话说，这里的各个节点所应用的是一个（其子节点的）兄弟节点链表，并且这些兄弟节点又各自引用了属于它们自己的那个兄弟节点链表（相关内容可以参考本章稍早前介绍list的黑盒子专栏）。因此，我们可以对清单2-7中的二叉树稍做修改，将其变成一个多路搜索树（multiway tree），具体如清单2-8所示。
清单2-8 多路搜索树类
在这里，独立属性val只是为相关的值（例如‘c’）提供了一个更具描述性的名称。当然，我们也可以根据自己的意愿对其进行随意调整。下面我们来演示一下该结构的具体访问方式：
并看看该树的具体结构图：
在该图中，kids和next属性被绘制成了虚线部分，而这棵树（原本被隐藏）的边则被绘制成了实线。需要注意的是，我们在这里实际上是玩了一个障眼法，即这里的"a"、"b"等字符串节点彼此之间并不是独立的。我们将它们视为它们父亲节点的标签。或许在某个更为复杂的树结构中，我们可能会考虑在kids以外设置其他独立的属性，以免再出现一个属性两种用途的情况。
通常在对某个树结构进行遍历时，我们所采用的代码应该会比上例中相关路径的硬编码更复杂一些（包括会使用循环、递归等技术）。关于多路树以及树的平衡问题，我们将会分别在第5、6章中做更详细的介绍。
2.3.4 多种表示法
尽管我们有大量的图表示法可用，但能被大多数学习算法的学生掌握的，也就是本章目前所介绍的这两类（包括其变化）而已。Jeremy P. Spinrad曾在他的《Efficient Graph Representations》一书中谈到，作为一个专门研究图结构表示法的计算机研究员，他对大部分这方面的入门文章都“特别不满”。这些文章对那些最知名的表示法（邻接矩阵与邻接列表）所做的正式定义还算可以，但在那些较为普通的表示法上，它们的解释往往就不那么如人意了。基于若干文章中所出现的失实论述，他特别例举了下面这段对图表示法的草包见解5：
在计算机中，一个图结构可以由邻接矩阵、邻接列表这两种方法来表示。其中，邻接矩阵工作时速度会更快一些，但其耗费的空间要比邻接列表多一些，因此我们的选择取决于哪一种资源更重要。
在Spinrad看来，这段论述存在着以下几个问题：首先，值得关注的图表示法有很多，并不只有这里所列出的这两种。例如边列表（或边集）就是其中之一，这种表示法列出的是图中所有节点对之间的边线（甚至还包括一些特殊的边对象）；还有关联矩阵（incidence matrices），这种方法所表示的是相关边线与节点之间的出入关系（也可用于多重图结构）；除此之外，还有类似于树（如之前所述）以及区间图（interval graphs，对此这里不予讨论）这样的特殊图结构表示法。总之，只要翻一翻Spinrad的书，您会发现实际上相关的表示法远比我们真正会用到的还要多得多。其次，所谓权衡空间与时间的想法也是个误导。有些问题用邻接列表解决的速度要比邻接数组快一些；而对于随机性图结构来说，邻接列表实际上所用的空间要比邻接矩阵多一些。
相较于依靠这种简单而空泛的句子堆砌而成的草包论述，我们更应该针对具体问题提出自己的思考。这里的主要指标就是我们任务的渐近性能。例如在邻接矩阵中，查询边（u，v）需要的时间为Θ(1)，遍历v 邻居的操作时间为Θ(n )；而到了邻接列表这种表示法中，两种操作所需的时间都为Θ(d (v ))，也就是说，它们的数量级与相关节点的邻居数量是同阶的。但如果相关算法的渐近复杂度在所有的表示法中都是一致的，那么我们可能就需要进行一些实验测试。关于这方面的内容，本章在前面已经讨论过了。或者在许多情况下，我们也可以直接选择那一个能让相关代码显得更清晰，更易于维护的表示法。
到目前为止，我们还有一种重要的图结构实现没有讨论，因为它更多时候是一个隐式的图实现。多数问题都有一个内在的图结构——乃至某种树结构——并且我们可以在没有明确为其构建表示法的情况下应用相应的图（或树）算法。在某些情况下，发生这种事往往都是在我们要使用自己程序以外的某种表示法时。例如，当我们要解析XML文档或者遍历某文件系统目录结构时，就可以直接使用现成的树结构以及现成的API。而在其他情况下，我们通常得自己来构建相关的图结构，但其过程可以是隐式的。例如，如果我们想为某个既定的魔方形态寻找一个最佳解决方案，就需要能定义出该魔方的状态，以及修改该状态的操作。即便我们不显式实例化并存储该魔方可能的所有形态，其可能状态仍隐式地形成一个图（或节点集），它以变化操作作为边线。接着，我们就可以对其使用诸如A*或双向Dijkstra（我们将在第9中详细讨论它们）这样的算法，查找能到达其解决状态的最短路径。在这种情况下，其邻居函数N (v )会在运行期间计算出相应的邻居节点，并将其整合成一个集合或其他可迭代对象返回。
在本章中，我们最后要接触的一类图结构叫作子问题图（subproblem graph）。这是一个非常有深度的概念，将来我们讨论各种不同算法技术时还会多次涉及它。这个概念简单地说就是，绝大部分问题应该都可以被分成若干个子问题，这些子问题在结构上往往都非常相似。因此，这些结构可以被看作相关子问题图中的节点，而它们间的依赖关系（也就是这些子问题之间的依存关系）就成为该图的边。尽管我们很少有机会直接在子问题图上运用相关的图算法（毕竟它更多时候只是一种概念或思考工具而已），但它往往能提供一些非常重要的分析。例如，分治法（第6章）以及动态规划（第8章）等技术就出自这些分析。
