摘要：图关联矩阵在关联矩阵表示的图中，矩阵的行表示顶点，列表示边。如图，顶点数是，边的数量是，用邻接矩阵表示图需要的空间是，而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。
定义
图和散列表、二叉树一样，是一种非线性数据结构。如图1所示，图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点，比如A和B、A和D是相邻的，而A和E不是相邻的。一个顶点相邻顶点的数量叫作度，比如A的度为3、D的度为4。路径指相邻顶点的一个连续序列，如ABEI、ACDG；简单路径指不包含重复顶点的路径（除环外），如ADG；环指首尾顶点相同的路径，如ADCA，环也属于简单路径。如果图中每两个顶点之间都有路径相连，则称该图是连通的。
如图2，如果图中的边具有方向，称该图为有向图。如果图中的边是双向的，则该图是强连通的，例如图3中的C和D是强连通的。图也可以是加权的，例如图3中的每条边都有权值。
图可以用来解决计算机中的很多问题，比如搜索图中的一个特定顶点或搜索一条特定边，寻找图中的一条路径（从一个顶点到另一个顶点） ，寻找两个顶点之间的最短路径，以及环检测。
图的表示图的表示方式有多种，没有绝对正确的表示方式，采用哪种方式取决于图的类型和待解决的问题。这里介绍三种方式：邻接矩阵、邻接表、关联矩阵。
邻接矩阵邻接矩阵用一个二维数组来表示图中顶点的连接情况；如果索引为i的节点和索引为j的节点连接，则array[i][j] === 1，否则array[i][j] === 0，如图4。邻接矩阵的缺点是，如果图不是强连通的，矩阵中就会出现很多0，从而计算机需要浪费存储空间来表示根本不存在的边。例如，即使某一顶点只有一个相邻顶点，也需要一整行来表示该顶点的连接情况，
邻接表由图中每个顶点的相邻顶点的列表所组成，如图5。只要能表示一对多的数据结构，都可以用来描述邻接表，比如多维列表（数组）、链表、散列表、字典等。
在大多数情况下，邻接表是更好的选择，但邻接矩阵也有其优点，比如要判断顶点A和B是否相邻，邻接矩阵比邻接表要快。
图5
关联矩阵在关联矩阵表示的图中，矩阵的行表示顶点，列表示边。如图6所示，我们使用二维数组来表示两者之间的连通性，如果顶点A是边E的入射点，则array[A][E] === 1；否则，array[A][E] === 0。
关联矩阵通常用于边的数量比顶点少的情况下，以节省空间和内存。如图6，顶点数是5，边的数量是6，用邻接矩阵表示图需要的空间是5*5=25，而使用关联矩阵表示图需要的空间是5*6=30。
图6
创建图类首先首先声明类的骨架：
function Graph() {
var vertices = [];
var adjList = new Dictionary();
}
其中Dictionary类的实现参考之前的文章字典。
我们使用数组 vertices 来存储图中所有顶点的名字，以及字典 adjList 来存储邻接表。字典将会使用顶点的名字作为键，邻接顶点列表作为值。
接下来实现向图中添加顶点的方法：
this.addVertex = function(v){
vertices.push(v);
adjList.set(v, []);
};
该方法接受顶点 v 作为参数。我们将该顶点添加到顶点列表 vertices 中，并且在邻接表中，设置顶点 v 作为键对应的字典值为一个空数组。
接着实现一个点到另一个点的连接：
this.addEdge = function(v, w){
adjList.get(v).push(w);
adjList.get(w).push(v);
};
这个方法接受两个顶点作为参数。首先，我们通过将 w 加入到 v 的邻接表中，添加了一条自顶
点 v 到顶点 w 的边。如果是有向图，则只需要该方法的第一行代码就行了。我们这里要实现无向图，我们需要添加一条自 w 向 v 的边，即该方法的第二行代码。
使用该图类进行简单的测试：
