用js来实现那些数据结构16（图02-图的遍历）
上一篇文章我们简单介绍了一下什么是图，以及用JS来实现一个可以添加顶点和边的图。按照惯例，任何数据结构都不可或缺的一个point就是遍历。也就是获取到数据结构中的所有元素。那么图当然也不例外。这篇文章我们就来看看如何遍历以及用js来实现图的遍历。
首先，有两种算法可以对图进行遍历：广度优先搜索（BFS）和深度优先搜索（DFS）。图的遍历可以用来寻找特定的顶点，可以寻找两个顶点之间有哪些路径，检查图是否是联通的，也可以检查图是否含有环等等。
在开始代码之前，我们需要了解一下图遍历的思想，也就是说，我们要知道如何去遍历一个图，知道了图遍历的方法方式，距离实现代码也就不远了。
图遍历的思想是：
1、必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于BFS和DFS两种算法，都需要明确给出第一个被访问的顶点。
2、完全探索一个顶点，要求我们查看该顶点的每一条边。对于每一条边所链接的没有被访问过的顶点，将其标注为被发现的，并将其加入到待访问顶点列表中。
那么，总结一下上面的两句话，首先，我们在遍历一个图的时候，需要指定第一个被访问的顶点是什么（也就是我们要在方法中传入第一个顶点的值）。然后呢.....我们需要知道三个状态：
一个是还未被访问的，也就是我还不知道有这么个顶点，也不知道它的边都去向哪里。
另外一个是已经访问过但未被探索过，就是说，我知道有这个顶点，但是我不知道它的边都去向哪里，连接着哪些顶点。
最后一个是访问过并且完全探索过。也就是我访问过该顶点，也探索过它有哪些边，它的边连接哪些顶点。
那么，我们就会在构造函数中用三种颜色来代表上面的三种状态，分别是白色（未被访问），灰色（已经访问过但未被探索过）和黑色（访问过并且完全探索过）；
还有另外一个要注意的地方，BFS和DFS在算法上其实基本上是一样的，但是有一个明显的不同——待访问顶点的数据结构。BFS用队列来存储待访问顶点的列表，DFS用栈来存储待访问顶点的列表。
好了，下面我们来上代码。（这里不会贴上所有的代码，只会贴上有关BFS和DFS的相关代码。）
如果你看到了这里，但是并不觉得自己可以耐心的把下面的代码看完，那么你看到这里就可以 结束所有有关于用js来实现数据结构的内容了。如果你还是想继续往下学习，那么希望你一定可以耐心看完整。
//引入前面章节学过的栈和队列，因为我们后面会用到。function Stack () {}; function Queue() {}; function Graph() { var vertices = []; var adjList = new Map(); //添加顶点的方法。 this.addVertices = function (v) {}; this.addEdge = function (v,w) {}; this.toString = function () {}; //初始化图中各顶点的状态（颜色）的私有方法，并返回该状态数组。 var initializeColor = function () { var color = []; for (var i = 0; i < vertices.length; i++) { color[vertices[i]] = 'white'; } return color; }; //简单的广度优先搜索算法，传入参数v是图中的某一个顶点，从此顶点开始探索整个图。 this.bfs = function (v,callback) { //为color状态数组赋值，初始化一个队列 var color = initializeColor(),queue = new Queue(); //将我们传入的顶点v入队。 queue.enqueue(v); // 如果队列非空，也就是说队列中始终有已发现但是未探索的顶点，那么执行逻辑。 while(!queue.isEmpty()) { // 队列遵循先进先出的原则，所以我们声明一个变量来暂时保存队列中的第一个顶点元素。 var u = queue.dequeue(); // adjList是我们的邻接表，从邻接表中拿到所有u的邻接顶点。 neighbors = adjList.get(u); //并把状态数组中的u的状态设置未已发现但是未完全探索的灰色状态。 color[u] = 'grey'; //我们循环当前的u的所有的邻接顶点，并循环访问每一个邻接顶点并改变它的状态为灰色。 for(var i = 0; i < neighbors.length; i++) { var w = neighbors[i]; if (color[w] === "white") { color[w] = 'grey'; //入队每一个w，这样while循环会在队列中没有任何元素，也就是完全访问所有顶点的时候结束。 queue.enqueue(w); } } // 完全访问后设置color状态。 color[u] = 'black'; // 如果存在回调函数，那么就执行回掉函数。 if