背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

连接万物的图

图

图是一种擅长表示关系的数据结构，它直观地表示了数据之间的连接方式。

图和树

树也是一种图。两种数据结构都包含互相连接的节点。

图和树的区别在于：虽然所有树都是图，但图未必都是树。

特别地，树中不能有环，并且所有节点都必须是连通的。而树则不能有环。如果一个图中存在环，它就不是树。

树还有一个特有的性质，就是每个节点都和所有其他节点直接或间接相连。但图有可能不完全相连。

图的术语

图有一些自己的术语。我们习惯了把每项数据叫作节点，但是用“图的方式”来说，每个节点叫作一个顶点。而顶点间的连线也有另一个名字：边。由一条边相连的顶点称作相邻顶点。有些人也会把相邻顶点称作邻居。

图的顶点有可能没有和任何顶点相连。但是，如果图中的所有顶点都以某种方式互相连接，我们就称它为连通图。

图的基本实现

考虑到代码结构，我们会用面向对象的类来表示图。但是有一点值得一提：也可以用哈希表（参见第8章）来表示基本的图。下面是用哈希表表示社交网络的基本Ruby实现。

friends = {
  "Alice" => ["Bob", "Diana", "Fred"],
  "Bob" => ["Alice", "Cynthia", "Diana"],
  "Cynthia" => ["Bob"],
  "Diana" => ["Alice", "Bob", "Fred"],
  "Elise" => ["Fred"],
  "Fred" => ["Alice", "Diana", "Elise"]
}

使用图，可以在O(1)步之内找到Alice的朋友。这是因为只用1步就可以在哈希表中找到任意键的值。

friends["Alice"]

这样就得到了包含Alice所有朋友的数组。

有向图

在某些社交网络中，关系不是相互的。例如，Alice可以在某个社交网络中关注Bob，但Bob不一定要关注Alice。可以用一个新图来表示这种关注关系，有向图。

仍然可以用上面的简单的哈希表来存储这些数据。

followees = {
  "Alice" => ["Bob", "Cynthia"],
  "Bob" => ["Cynthia"],
  "Cynthia" => ["Bob"]
}

唯一的区别在于，这里用数组表示每个人关注的对象。

面向对象的图实现

前面介绍了如何用哈希表实现图，接下来会采用面向对象实现。下面是Ruby中图的面向对象实现的基础版本。

class Vertex
  attr_accessor :value, :adjacent_vertices
  def initialize(value)
    @value = value
    @adjacent_vertices = []
  end
  def add_adjacent_vertex(vertex)
    @adjacent_vertices << vertex
  end
end

Vertex类有两个主要属性，即value和adjacent_vertices数组。在社交网络的例子中，每个顶点表示一个用户，value可能是一个包含该用户姓名的字符串。在更复杂的应用中，我们可能会在一个顶点中存储多项数据，比如用户的其他账户信息。

adjacent_vertices数组包含和该顶点相连的所有顶点。可以用add_adjacent_vertex方法来为已知顶点添加一个新的相邻顶点。

可以像下面这样使用这个类来构建一个表示关注关系的有向图。

alice = Vertex.new("alice")
bob = Vertex.new("bob")
cynthia = Vertex.new("cynthia")
alice.add_adjacent_vertex(bob)
alice.add_adjacent_vertex(cynthia)
bob.add_adjacent_vertex(cynthia)
cynthia.add_adjacent_vertex(bob)

图的搜索

图最常用的操作之一是搜索特定顶点。

在使用图的时候，“搜索”有几种含义。图的“搜索”的最简单的含义就是找到图中某处特定顶点。这和在数组中查找一个值，或者在哈希表中查找键-值对类似。

不过，图的搜索还有一种更具体的含义：如果可以访问图的一个顶点，那么需要找到另一个和它以某种方式相连的顶点。

路径是一个正式的术语，表示从一个顶点到另一个顶点的某种边的序列。

图的搜索（现在你知道它是指从一个顶点找到另一个顶点了）有很多使用情景。

可能其中最明显的应用就是在连通图中搜索特定顶点。

在此情况下，即便只能访问一个随机顶点，搜索也可以找到图中的任意顶点。图的搜索的另一个用途是判断两个顶点是否相连。例如，我们可能想知道Alice和Irena在这个网络中是否以某种方式相连。搜索可以给出这个问题的答案。

图的搜索有两种著名的方法：深度优先搜索和广度优先搜索。两种方法都可以完成我们的任务，但是它们在特定场合有着不同的优势。

总结

图是解决关系问题的强有力的工具。除了能加速代码，它还能解决复杂问题。

图有很多有趣且有用的算法：最小生成树、拓扑排序、双向搜索、Floyd-Warshall算法、Bellman-Ford算法、图的着色等。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。