在计算机科学中，图是一种网络结构的抽象模型，它是一组由边连接的顶点组成。一个图G = (V, E)由以下元素组成：
V：一组顶点
E：一组边，连接V中的顶点
下图表示了一个图的结构：
在介绍如何用JavaScript实现图之前，我们先介绍一些和图相关的术语。
如上图所示，由一条边连接在一起的顶点称为相邻顶点，A和B是相邻顶点，A和D是相邻顶点，A和C是相邻顶点......A和E是不相邻顶点。一个顶点的度是其相邻顶点的数量，A和其它三个顶点相连，所以A的度为3，E和其它两个顶点相连，所以E的度为2......路径是一组相邻顶点的连续序列，如上图中包含路径ABEI、路径ACDG、路径ABE、路径ACDH等。简单路径要求路径中不包含有重复的顶点，如果将环的最后一个顶点去掉，它也是一个简单路径。例如路径ADCA是一个环，它不是一个简单路径，如果将路径中的最后一个顶点A去掉，那么它就是一个简单路径。如果图中不存在环，则称该图是无环的。如果图中任何两个顶点间都存在路径，则该图是连通的，如上图就是一个连通图。如果图的边没有方向，则该图是无向图，上图所示为无向图，反之则称为有向图，下图所示为有向图：
在有向图中，如果两个顶点间在双向上都存在路径，则称这两个顶点是强连通的，如上图中C和D是强连通的，而A和B是非强连通的。如果有向图中的任何两个顶点间在双向上都存在路径，则该有向图是强连通的，非强连通的图也称为稀疏图。
此外，图还可以是加权的。前面我们看到的图都是未加权的，下图为一个加权的图：
可以想象一下，前面我们介绍的树和链表也属于图的一种特殊形式。图在计算机科学中的应用十分广泛，例如我们可以搜索图中的一个特定顶点或一条特定的边，或者寻找两个顶点间的路径以及最短路径，检测图中是否存在环等等。
存在多种不同的方式来实现图的数据结构，下面介绍几种常用的方式。
邻接矩阵在邻接矩阵中，我们用一个二维数组来表示图中顶点之间的连接，如果两个顶点之间存在连接，则这两个顶点对应的二维数组下标的元素的值为1，否则为0。下图是用邻接矩阵方式表示的图：
如果是加权的图，我们可以将邻接矩阵中二维数组里的值1改成对应的加权数。邻接矩阵方式存在一个缺点，如果图是非强连通的，则二维数组中会有很多的0，这表示我们使用了很多的存储空间来表示根本不存在的边。另一个缺点就是当图的顶点发生改变时，对于二维数组的修改会变得不太灵活。
邻接表图的另外一种实现方式是邻接表，它是对邻接矩阵的一种改进。邻接表由图中每个顶点的相邻顶点列表所组成。如下图所示，我们可以用数组、链表、字典或散列表来表示邻接表。
我们还可以用关联矩阵来表示图。在关联矩阵中，矩阵的行表示顶点，列表示边。关联矩阵通常用于边的数量比顶点多的情况下，以节省存储空间。如下图所示为关联矩阵方式表示的图：
下面我们重点看下如何用邻接表的方式表示图。我们的Graph类的骨架如下，它用邻接表方式来实现无向图：
class Graph { constructor () { this.vertices = []; // 用来存放图中的顶点 this.adjList = new Dictionary(); // 用来存放图中的边 } // 向图中添加一个新顶点 addVertex (v) {} // 向图中添加a和b两个顶点之间的边 addEdge (a, b) {} }