图数据结构入门

在这篇文章中,我们将探索像图这样的非线性数据结构。我们将介绍其核心概念和典型应用。

你可能正在使用使用图(和树)数据结构的程序。比方说,你想知道你工作的地方和家之间的最短路径,你可以使用图算法来获得答案!我们将探讨这个和其他有趣的挑战。

在上一篇文章中,我们探索线性数据结构,如数组、链表、集合、栈等。这篇文章是建立在我们已学到的知识之上的。

这篇文章是此教程系列的一部分:

给初学者的数据结构及算法之路

  1. 算法时间复杂度及大O表示法简介

  2. 每个程序员必知的三个时间复杂度

  3. 给初学者的数据结构:数组、哈希表以及链表

  4. 给初学者的数据结构之图 <== 你在这里

  5. 给初学者的数据结构之树

  6. 自平衡二叉搜索树

  7. 附录I: 递归算法分析

以下是我们将在本文中介绍的操作的摘要:

 Adjacency ListAdjacency Matrix
SpaceO(|V| + |E|)O(|V|2)
addVertexO(1)O(|V|2)
removeVertexO(|V| + |E|)O(|V|2)
addEdgeO(1)O(1)
removeEdge (using Array)O(|E|)O(1)
removeEdge (using HashSet)O(1)O(1)
getAdjacentsO(|E|)O(|V|)
isAdjacent (using Array)O(|E|)O(1)
isAdjacent (using HashSet)O(1)O(1)

图的基础知识

图是一种数据结构,其中的节点可以具有零个或多个相邻元素。两个节点之间的连接称为边。 节点亦可称为顶点。

度是与顶点相关联的边的个数。例如,紫色顶点的度数为3,而蓝色顶点度数为1.

如果边是双向的,我们就有了一个无向图。 但如果边有方向,那么我们就有一个有向图或简单图。 你可以将其视为单行道(有向)或双向街道(无向)。

顶点可以有关于自己的边,例如蓝的顶点,称之为自循环。

图可以具有循环,这意味着如果要遍历节点,则可以多次访问同一节点。 没有循环的图称为非循环图。

此外,非循环无向图称为树。 我们将在下篇中深入讲解树。

并非所有顶点都必须在图中连接。 可以有孤立的节点甚至是分离的子图。 如果所有节点都至少有一个边,那么我们有一个连通图。 当所有节点都连接到所有其他节点时,我们就有了完全图。

对于完全图,每个节点必须有#nodes - 1个边。 在前面的例子中,我们有7个顶点,因此每个节点有6个边。

图的应用

当边具有已分配给它们的价值/费用时,我们说我们有一个加权图。如果没有加权值,我们可以假设它是1。

加权图具有许多应用场景,具体取决于你需要解决问题的域。仅举几例:

通常,图有很多现实世界的应用,比如: 

我们刚刚学习了图的基础知识及其相关的一些应用场景。现在让我们学习如何在代码中表示图。

表示图

有两种主要用于表示图的方式:

  1. 邻接表

  2. 邻接矩阵

让我们用以下有向图作为示例分析一下:

此有向图有4个节点。当一个顶点有指向自身的链接时(比如a)则称之为自循环

邻接矩阵

邻接矩阵是一种使用二维数组(NxN矩阵)来表示图的方式。针对顶点的相交的情况,如果二者是连接的,我们将添加1(或者其他权重),否则设置为0或-。

使用之前的示例,我们可以构建以下邻接矩阵:

需要注意的是无向图的邻接矩阵总是以对角线为轴对称的。然而,在有向图中并不是如此(例如我们的示例中的有向图)。正如你所看到的,该矩阵从水平和垂直方向列出了所有节点。如果连接比较少,我们称之为稀疏图;如果连接很多(接近最大连接数目),我们称之为稠密图。如果达到了所有可能的连接,我们就拥有了完全图。

查找两个顶点之间的时间复杂度如何呢?

在邻接矩阵中查询两个顶点是否相连的复杂度是O(1).

空间复杂度如何呢?

将图保存为邻接矩阵的空间复杂度是O(n2),其中n是顶点的数目。也可表示为 O(|V|2)。

添加一个顶点的运行时间如何呢?

顶点被保存在VxV的矩阵中。因此,每次添加顶点时,矩阵必须被重构为新的V+1xV+1

在邻接矩阵中添加顶点的复杂度是O(|V|2)

那么如何获得相邻的顶点呢?

既然邻接矩阵拥有一个VxV的矩阵,为了获得与给定顶点相邻的所有节点,我们必须进入顶点所在的行,然后获取它与其他顶点相连的所有边。

在之前的示例中,假设我们需要获得所有与b相邻的顶点。我们需要获取存储b与其他所有顶点连接信息的行数据。


我们需要遍历所有节点,

在邻接矩阵中获取相邻节点的时间复杂度是O(|V|)

假设你需要将Facebook网络用图来表示。你可能需要创建一个20亿x20亿的矩阵,其中多数节点是空的!没有人可以认识其他所有人,通常至多几千人而已。

通常,我们需要处理稀疏图的矩阵,因为这种矩阵将浪费大量存储空间。这就是为什么在多数实现中我们使用邻接表而不选择邻接矩阵的原因了。

邻接表

一种表示图的比较通用的方法是使用邻接表. 每一个节点都包含一个列表, 这个列表中的每一个元素都是与该节点相连的.

可以使用Array(或HashMap)作为邻接表容器来表示图, 容器中的元素就是图节点. 而每一个节点实体又包含一个列表(数组,链表,集合等), 来包含与该节点邻接的节点.

例如,在上面的图中, a 与 b 相连接, 同时 a 又连接到自身. 接下来 b 与 c 相连接, 如此继续下去.

给定邻接表中两个节点是否相连的复杂度是O(n), 其中 n 代表顶点的数量. 也可以写为O(|V|). 你可以想象, 如果你想知道一个节点与另一个节点是否相连, 你必须遍历这个列表.

那么空间复杂度又如何呢?

将图存储为邻接表的空间复杂度是O(n), 其中 n 是顶点数与边数的和. 也可以表示为O(|V| + |E|).

使用邻接表作为图表示方式的HashMap实现

邻接表是图的最通用的一种表示方式, 也有很多方式可以实现邻接表.

其中最简单的一种实现方式就是HashMap. 节点值可以作为key, value值是一个邻接数组.

增加/移除图中的顶点经常需要以下操作:

增加/移除顶点也需要更新邻接表.

假设我们想移除顶点b, 我们可以这样做: delete graph['b'];, 可是我们还必须移除邻接表中顶点d和顶点a对b的引用.

每次我们移除一个节点, 我们都必须迭代所有的节点列表, 复杂度是 O(|V| + |E|). 有没有更好的方法呢? 我们后面再回答这个问题. 首先让我们一起来以一种更"面向对象"的方式来实现我们的表, 这样做swap操作就会更容易些.

邻接表图"面向对象"实现

我们先新建一个 Node 类, 顶点值和对应的邻接顶点作为类成员. 然后创建一个帮助函数来对表进行添加/移除邻接顶点的操作.

然后我们让它变得更快更正确更好. 这里你可以看到: 增加 adjacent 时间复杂度是O(1), 移除 adjacent 的时间复杂度是 O(|E|). 那么如果使用HashSet来代替数组呢? 那将是 O(1). 但是我们先让它可以运行, 后面再做优化.

好了, 现在我们有了 Node 类, 接下来让我们构建 Graph 类, 以及可以实现添加/移除顶点和边的操作.

Graph.constructor

我们需要知道的第一件事是这个图是个有向图还是无向图. 在添加边时这两种类型的图会有所不同.

图 --- 添加边操作(Graph.addEdge)

增加一条边需要两个节点。一个是源节点,一个是目的节点。

我们增加一条从源顶点到目的顶点的边。 如果是一个无向图, 那么我们还要增加一条从目标点到源节点的边,因为它是双向的。

为一个图的邻接表增加一条边的时间复杂度是O(1)

如果我们要增加边时,对应的节点不存在,我们就需要先创建它们。接下来我们看如何实现:

图 --- 添加顶点操作(Graph.addVertex)

创建节点的方法就是将它添加到 this.nodes Map中。Map存储一个键值对,key 是顶点值,value 是Node类的实例。下面让我们看一下代码:

如果节点已经存在,我们不需要覆盖它的值,所以我们首先要检查节点是否存在,如果不存在,就创建。

对图的邻接表添加顶点的时间复杂度是 O(1)。

图 --- 移除顶点(Graph.removeVertex)

从图中移除一个节点有点复杂, 我们必须检查要被删除的节点是否是一个正在使用中的邻接点。

 

我们必须遍历每一个顶点和它的邻接点(就是边)。

从图的邻接表中移除一个顶点的时间复杂度是 O(|V| + |E|)。

最后, 让我们看如何删除一条边。

图 -- 移除边(Graph.removeEdge)

移除一条边比较简单直接, 类似于 addEdge 。

addEdge 和 removeEdge 的主要区别是:

因为 removeAdjacent 必须遍历所有的邻接顶点,所以我们有以下时间复杂度:

从图的邻接表中移除一条边的时间复杂度是 O(|E|)。

下面我们开始看看如何在节点中搜索特定的值。

广度优先搜索(BFS) -- 图搜索

广度优先搜索是遍历图的一种方法,它首先搜索给定初始顶点的所有邻接节点。

我们看看代码如何实现:

如你所见,我们用一个Queue来存储访问过的节点。队列是先进先出的(FIFO)。

我们也使用了JavaScript的生成器(generators),注意函数名前的*符号。我们用一个生成器(generator)来一次一个地迭代它们的值。这个对大的图(成千上万的节点)是非常有帮助的。因为在大多数情况下,你不需要访问每一个节点。

下面让我们看看如何使用BFS:

你也可以发现 BFS 的更多的例子: test cases。下面我们看看深度优先搜索 (DFS) 。

深度优先搜索(DFS) -- 图搜索

深度优先搜索是遍历图的另一种方法,它首先访问给定顶点的第一个邻接节点,然后访问领接节点的第一个发现的节点,如此递归下去。

实现 DFS 的代码类似 BFS ,不过用 Stack 来代替 Queue 。

下面测试一下我们的图:

从以上结果可以看出,BFS 和 DFS 的输出是一样的,只不过节点的访问顺序是不同的。BFS 是从 1 到 10 的自然顺序, 而 DFS 是对每一个节点先进行深入搜索。

图的时间和空间复杂度

我们已经见识了图的一些基本操作。如何添加和删除顶点和边。 以下是我们迄今为止所涵盖内容的摘要:

 邻接表邻接矩阵
SpaceO(|V| + |E|)O(|V|2)
addVertexO(1)O(|V|2)
removeVertexO(|V| + |E|)O(|V|2)
addEdgeO(1)O(1)
removeEdge (using Array)O(|E|)O(1)
removeEdge (using HashSet)O(1)O(1)
getAdjacentsO(|E|)O(|V|)
isAdjacent (using Array)O(|E|)O(1)
isAdjacent (using HashSet)O(1)O(1)

如你所见,邻接表在几乎所有函数上都更快。邻接矩阵唯一优于邻接表的是检查节点是否与其他节点相邻,但如果我们将实现从 Array 更改为 HashSet ,我们也可以在常量时间内实现之:)

总结

正如我们所看到的,图可以帮助模拟许多现实场景,如机场、社交网络、互联网等。我们介绍了一些最基本的算法,如广度优先搜索(BFS)和深度优先搜索(DFS)。此外,我们还讨论了不同实现方案之间的权衡,例如邻接表和邻接矩阵。我们将在另一篇文章中介绍许多其他应用,例如查找节点之间的最短路径和不同的令人振奋的图算法。