（有向）图是由节点通过箭头（边）连接而成的集合。节点和边都可以包含数据。下面是一些图的例子：

图在软件工程中无处不在：

1. 包依赖关系构成有向图，模块导入也是如此。
2. 互联网是由网页之间的链接构成的图。
3. 模型检测器通过探索所有可能配置的“状态空间”来分析软件。节点是状态，边是状态之间合法的迁移。
4. 关系型数据库就是图，其中节点是记录，边是外键。
5. 图是链表、二叉树和哈希表的一般化形式。¹

图在业务逻辑中也十分常见。带有引用的白皮书构成了引文图。交通网络是路线图。社交网络是人际关系的图。如果你做软件开发的时间足够长，总会在某个地方遇到图。

我到处都能看到图，并用它们来分析各种系统。与此同时，我却很怕在代码中真的去使用图。任何主流语言中几乎都没有对图的支持。没有任何一门语言把它作为内置类型，很少有语言在标准库里提供图，很多语言的生态中甚至没有健壮的第三方库。大多数时候，我不得不从零开始实现图。软件工程师本可以经常用到的图，与我们的编程生态对图的支持之匮乏之间，存在着巨大的落差。那些图类型都去哪了？

随着我在工作中遇到越来越多的图，这个问题对我来说也变得越来越有意思。于是去年年底，我终于开始寻找答案。我在我的新闻通讯上发了一则征集，邀请有相关专业背景的人——图算法的发明者、语言委员会成员、图库维护者——来与我交流。我原本预计会采访十几个人，但最后只聊了四位：

1. Zayenz：Gecode 约束求解器的前核心开发者，自称“实现过所有图算法”
2. Bradford：Nosey Parker 安全库的作者，并发明了几种新的图算法
3. Nicole：前图数据库工程师
4. Kelly：Python 图库 NetworkX 的维护者兼编译器开发者。

在这四个人都给出了相似的回答后，我便停止采访，开始动笔。

原因

设计选择太多

到目前为止，我描述的都是有向图。还有无向图，其中的边没有方向。有向图和无向图又都可以是简单图，即两个节点之间最多只有一条边，也可以是多重图，即两个节点之间可以有多条边。而在这些类型之上，还有超图，其中一条边可以连接三个或更多节点，以及 ubergraph，其中边可以指向其他边。对于每一种可能的变体，你都还要做更多选择：是只给节点分配 ID，还是也给边分配？节点里能存什么数据，边里又能存什么？对于一个库来说，这需要做太多决定了！

但等一下，这些区分真的重要吗？简单图不过是退化的多重图，而无向边也可以无损地转换成两条有向边。一门语言完全可以只提供有向超多重 ubergraph，然后让用户按需自行约束。

这样做有两个问题。首先，它会改变接口，比如某些操作返回的是单个值还是列表。其次，正如我稍后会谈到的，图算法的性能是一个非常现实的考量，而这些特例真的很重要。Kelly 举了最大权匹配的例子。如果你知道图是“二分图”，就可以用一种特定的快速算法来求匹配，而对于其他图，则必须使用更慢、更通用的算法。

这又回到了“算法分派问题”。给定一个问题 P、一张图 G，以及在 G 上解决 P 的算法 A、B、C……你该运行哪一个？如果我们不知道 G 是不是二分图，而算法 C 只适用于二分图，那我们能花多少时间来判断 G 到底是不是二分图呢？——Kelly

完美的图库会支持许多不同种类的图。但这会占用本可用于支持人们想用图来做什么的时间。图算法出了名的难以写对。在这篇文章中，Python 的发明者自己实现了一个 find_shortest_path 算法。它先后被修正了五次才改对！

我对比过的每一个 pagerank 实现都是错的。——Nicole

那么，库应该自带哪些算法呢？“人们想用图来做的事情多得离谱，”Kelly 告诉我。这与我的经验相符，也与我所有受访者的经验一致。有时图似乎太过强大，其所有可能性都超出了我的理解。“问题在于，”Kelly 说，“你在哪里划线？”

对 NetworkX 来说，“这条线”大约是 500 种不同的图算法，光这些算法本身就占了近 6 万行代码。相比之下，由 300 个包组成的整个 Python 标准库，总共还不到 60 万行。²

有这些背景在，标准库中看不到图也就不足为奇了。语言维护者必须决定支持哪几种图、为哪些拓扑结构做特化、以及包含哪些算法。把这些维护工作推给第三方是合理的。这已经是语言发展的主流趋势；即便是以“自带电池”著称的 Python，也在移除 20 块电池。

第三方可以在如何设计图以及包含哪些算法上做出有主见的选择。但随后他们又会面临下一个问题：一旦有了图的接口，该如何表示它？

实现选择太多

假设我们只支持最精简的简单有向图：节点有标识，边没有，节点和边都不附带任何数据。我们该如何编码这样一张图？

以下是编程语言在内部存储它的四种可能方式：

1. 边列表：[[a, b], [b, c], [c, a], [c, b]]
2. 邻接表：[[b], [c], [a, b]]
3. 邻接矩阵：[0 1 0; 0 0 1; 1 1 0]
4. 一组通过相互引用关联的三个结构体

不同的图操作在不同的表示方式下，性能特征也不同。以一张有 100 个节点、200 条边的有向图为例。如果使用邻接矩阵表示，我们需要一个 100×100 的矩阵，其中包含 200 个 1 和 9800 个 0。如果改用边列表，我们只需要 200 对节点。取决于编程语言和优化程度，这可能是 20 倍甚至更大的内存差异。

现在再看一张有 100 个节点、8000 条边的图，尝试判断节点 0 和节点 93 之间是否存在一条边。在矩阵表示中，这只需对 graph[0][93] 做一次 O(1) 查找。而在边列表表示中，则需要遍历全部 8000 条边，时间复杂度为 O(|edge|)。³

只有少量边的图是稀疏图，而几乎包含所有可能边的图是稠密图。同一个程序可能需要在两种图拓扑上执行这两种操作：如果你正在从外部数据构建图，起初可能是稀疏图，之后可能变得稠密。对于图的内部表示而言，并不存在“最优选择”。

而上述所有麻烦，还仅仅是针对最精简的有向图！那要实现节点数据呢？边数据呢？不同类型的节点和边呢？大多数第三方库大致可分为两类：

1. 提供单一的、功能丰富的类型，以牺牲效率为代价覆盖所有用例。NetworkX 将图存储为字典的字典的字典，以便节点和边都能拥有任意数据。⁴

2. 为每种表示提供独立的图类型，并依赖用户将节点和边数据与图类型分开存储。

第二种情况的一个例子是 Petgraph，这是 Rust 最受欢迎的图库。Petgraph 针对不同用例提供了 graph、graphmap 和 matrix_graph。Bradford 在 Nosey Parker 中使用了 Petgraph，这是一个用于扫描整个 Git 仓库历史中敏感信息的安工具。他的基准测试图是 CPython，拥有 25 万次提交和 130 万个对象，但每个提交节点只有少量边。他选择了邻接表。

支持多种表示有一个严重的缺点：添加算法时需要做更多工作。如果为每种图表示都单独写一版算法，维护负担就会增加两三倍。如果转而为多态类型编写通用抽象，那么库的性能就会下降。一位受访的程序员估计，手写的图算法可能比通用算法快 20 倍甚至更多。

而这正触及了每一位受访者最主要的抱怨。

性能太重要

“通用的”图实现往往不够用。——Bradford

这是最关键的一点。

许许多多图算法都是 NP 完全甚至更难的。⁵虽然 NP 完全问题对于大规模问题通常仍是可处理的，但图可能构成极其庞大的问题。表示方式的选择对完成速度起着重要作用，算法实现的具体细节也是如此。

我聊过的每个人对此都有亲身经历。在 Nosey Parker 中，Bradford 需要为每次提交重建文件系统的快照，这意味着要遍历对象图。所提供的四种图遍历器没有一种能扩展到他的用例。相反，他不得不临时设计了一种“半新颖”的图遍历算法，将内存占用降低了上千倍。

我很快就用 [petgraph] 做出了一个可运行的概念验证，但随后……这正是性能约束与现实相遇的情况之一。——Bradford

Zayenz 提出了另一个问题：如果图本身就大到无法处理怎么办？他举了求解15 拼图的例子。这是通过在状态空间上运行 A* 搜索来完成的。一个拥有超过 20 万亿个状态的状态空间。

如果你把所有节点都生成出来，你就已经输了。——Zayenz

Zayenz 主持过一个向 Gecode 约束求解器添加图的研究项目。他们最终发现，通用图类型根本无法与为具体问题量身定制的表示方式竞争。

即便是完全围绕运行复杂图算法而设计的图数据库，也在这个问题上举步维艰。图数据库工程师 Nicole 向我讲述了优化即便是基本图操作时所面临的一些挑战。

如果你在做遍历，要么限制深度，要么就得接受会访问整张图。当你做深度搜索，比如“从这里向外走三步并判断路径是否存在”时，你实际上就是在承诺要访问相当多的数据。——Nicole

离开那份工作后，她做起了图查询性能顾问。这通常意味着要从图数据库迁移出去。她向我讲述了其中一个项目：为了加速图查询，她保留了一项计算不变，其余部分则重写为 MapReduce 过程。“这样理解起来要困难得多，”她说，“但确实能在一夜之间跑完。”

所有这些都意味着，如果你有想要解决的图问题，就需要对数据表示和算法的具体细节拥有大量控制权。你根本无法承受在性能上的任何浪费。

结论惊人地一致

那么，我们之所以缺乏广泛的图支持，原因在于：

• 图有很多不同种类
• 每种图都有很多不同表示方式
• 图算法有很多种
• 图算法的性能对图的表示和实现细节非常敏感
• 人们在非常大的图上运行非常昂贵的算法。

这解释了为什么语言不在标准库中支持图：太多的设计决策、太多的权衡、以及太重的维护负担。它解释了为什么程序员可能会回避第三方图库，因为它们要么过于受限，要么太慢。它也解释了为什么程序员除非在极端情况下，否则可能不愿以图的方式思考问题：处理图实在太难了。

自从开始这项研究以来，我在工作中又遇到了几个新的图问题。我依然喜欢将系统分析为图，也依然害怕去实现它们。但现在我明白为什么其他人也同样害怕了。感谢阅读！

感谢 Predrag Gruevski 在研究上的帮助，感谢 Lars Hupel、Predrag Gruevski、Dan Luu 和 Marianne Bellotti 提供的反馈，也感谢所有接受采访的人。如果你喜欢这篇文章，欢迎订阅我的新闻通讯！我每周都会在那里发表新文章。

我为企业提供形式化方法培训，帮助软件开发变得更快、更便宜、更安全。在这里了解更多。

附录：带有图类型的语言

图查询语言

图查询语言（GQL）⁶之于图数据库，就如同 SQL 之于关系型数据库。并没有被广泛使用的标准，但其中最流行的两种是用于查询 RDF 三元组的 SPARQL 和 Neo4j 的 Cypher。颇具讽刺意味的是，GraphQL 不是图查询语言，它的名字来源于与 Facebook Graph Search 的关联。我认为图数据库本身与编程语言中的图大多是不同的事物，但它们的查询语言展示了图在编程语言中可以如何运作。

所有 GQL 与 SQL 的主要区别在于，“连接”（关系）是一等实体。想象一个包含电影和人物的数据集，其中人物在电影中出演、导演或担任制片。在 SQL 中，你会将每种关系实现为多对多表，这使得查询“谁出演了电影 X”很容易，但查询“谁在电影 Y 中担任过任何角色，以及是什么角色”就很困难。在 SPARQL 中，关系就是边，使得同样的查询变得容易。

PREFIX mv: <your_movie_ontology_URL>
SELECT ?person ?role
WHERE {
    ?person ?role mv:casablanca.
}

Cypher 也有类似的结构。GQL 还可以操作边：反转它们、将它们组合在一起、求传递闭包等等。如果我们想找出所有与 Kevin Bacon 有某种间隔度数的演员，可以这样写

PREFIX mv: <your_movie_ontology_URL>
SELECT ?a
WHERE {
    mv:kbacon (:acted_in/^:acted_in)+ ?a.
    # a/b = join two lookups
    # ^a = reverse a
    # a+ = transitive closure
}

SPARQL 无法给出路径长度，也无法在路径上进行计算，比如收集连接两位演员的电影链。支持这些功能的 GQL 要复杂得多。

我考察 GQL 的主要收获是，支持图的编程语言需要提供一组有用的遍历原语。有趣的是，形式化规约语言 Alloy 为其“关系”数据类型提供了所有这些原语。出于这个原因，我发现在 Alloy 中处理图的表示比在真正的编程语言中要容易得多。话虽如此，这些原语都适用于带标签的边，可能不适用于其他图的表示方式。

标准库中包含图的通用语言

Python 在 2020 年新增了 graphlib。根据这里的讨论，原因是拓扑排序是一种“基础算法”，并且它对于“纯 Python 实现的 MRO（方法解析顺序）逻辑”会很有用。Graphlib 除了 TopologicalSorter 之外没有任何其他方法，它只接受以节点字典形式表示的图。不寻常的是，节点字典的方向是反向的：图 a -> b 被表示为 {b: [a]}。

截至 2023 年，CPython 中没有任何地方使用了 graphlib，在 GitHub 上引用它的文件不到 900 个。相比之下，同样在 2020 年加入的 zoneinfo 出现在 6000 多个文件中，而 def topological_sort( 这一项就出现了 4000 次。我猜其中很多是 2020 年之前的代码。粗略浏览表明，所有这些自定义的拓扑排序所接受的图表示都与 graphlib 不同，因此无论如何都无法转换。图的表示方式很重要。

我发现另外两门在标准库中带有图类型的语言是：Erlang 和 SWI-Prolog。我不懂这两门语言，也无法判断它们是何时加入的；至少对 Erlang 来说，是在 2008 年之前。我曾联系过一位 Erlang 核心语言委员会的成员，但没有收到回复。

图语言

“一切皆图”的编程语言，就像 bash 中一切皆字符串、Lisp 中一切皆列表一样。一些例子包括 GP2 和 Grape。根据我与该领域一些人的通信，目前这仍是高度学术化的方向。

数学软件语言

Mathematica、MATLAB、Maple 等都以某种形式拥有图库。我可不想为此支付数千美元的授权费用去进一步了解。

更新 2024-03-18

我已将收到的关于本文的一些评论收集在这里。

1. 不是开玩笑，哈希表就是二分图。这一点曾被用于证明布谷鸟哈希操作的性能。 ^[返回]
2. 这两个计算都是我用 cloc 1.96 得出的。我在 networkx/networkx/algorithms（56989）和 cpython/Lib（588167）上运行了 cloc。整个 networkX 库大约是 9 万行代码。 ^[返回]
3. 你可以通过保持边列表有序并进行 O(log(|e|)) 二分查找来提高效率，代价是使边的插入开销更大。 ^[返回]
4. NetworkX 提供了将图转换为其他表示的函数，但并不直接支持对那些表示进行操作。 ^[返回]
5. 在 21 个经典的 NP 完全问题中，有 14 个是图问题。 ^[返回]
6. 不要与仍在制定中的拟议 GQL 标准 GQL 语言混淆。 ^[返回]