图

图是基本数据结构中最复杂的一种，也是最常用的。经常：

• 在地图应用中，计算最佳导航路由。
• 在社交平台中，表示好友关系。
• 在网络中，表示拓扑结构。
• 或者大部分表示关系或网络的系统中。

定义

图是由一组节点，和连接节点的边构成的非线性数据结构。其中节点又叫作顶点。

我们之前介绍的树，其实就是图的一种，只是在树中，只有一个根节点，并且节点之间不会形成环。

分类

根据图的节点之间的边是否有方向，可以分为有向图和无向图。

• 在有向图中，访问节点只能按照指定的方向进行。
• 在无向图中，可以以任意方向访问节点，因此它也容易构成环。

根据图的节点是否都可以遍历到，还分为连通图和非连通图（或叫作隔离图）：

• 连通图中的每个节点都有连接的边。
• 非连通图则是由多个独立的图构成，它们之间没有边连接。

另外，如果连接节点的边还包含有额外信息，例如长度，那么这种图称为加权图。

代码表示

使用代码表示图有多种方式，常见的有：

• 使用邻接矩阵。
• 使用邻接节点数组。

这两种形式。​

在邻接矩阵表示法中，图是由一个 N*N 的二维数组表示的，N 为节点数量，行表示起始节点，列表示目标节点，如果起始节点和目标节点之间有边进行连接，那么就把该位置的元素设置为 1，否则设置为 0，或者也可以使用 true 和 false 表示。 对于无向图，矩阵是对称的，有向图则不一定。

无向图：

	1	2	3	4
1	0	1	0	1
2	1	0	0	1
3	0	0	0	1
4	1	1	1	0

有向图：

	1	2	3	4
1	0	1	0	1
2	0	0	0	1
3	0	0	0	0
4	0	0	1	0

在邻接节点数组表示法中，节点使用对象或类表示，每个节点都保存了和它直接相邻的节点所构成的数组，这种结构和树类似。

JavaScript 实现

这里我们看一下最简单的无向图的 JavaScript 实现，使用邻接节点数组的形式。 首先我们使用一个 Node class 表示图的节点，它里边有节点的值，和邻接节点数组属性：

class Node {
  constructor(value, neighbors = []) {
    this.value = value;
    this.neighbors = neighbors;
  }
}

它也是一个递归的结构，邻接节点数组中的元素也是 Node 类型，是当前节点能够连接到的相邻节点。 然后我们使用一个 Graph class 表示图本身：

class Graph {
  constructor(nodes) {
    this.nodes = nodes;
  }
}

它包含这个图中的所有节点。这个就是使用邻接节点数组表示图的基本结构，看起来很简单，而对于图的操作，每一项都比较繁琐。