//队列

		var Queue = (function(){

		    var item = new WeakMap();

		    class Queue{

		        constructor(){

		            item.set(this,[]);

		        }

		        enqueue(ele){

		            var ls = item.get(this);

		            ls.push(ele);

		        }

		        dequeue(){

		            var ls = item.get(this);

		            return ls.shift();

		        }

		        size(){

		            var ls = item.get(this);

		            return ls.length;

		        }

		        front(){

		            var ls = item.get(this);

		            return ls[0];

		        }

		        isEmpty(){

		            var ls = item.get(this);

		            return !ls.length;

		        }

		        print(){

		            var ls = item.get(this);

		            for(var i = 0; i < ls.length; i++){

		            console.log(`${ls[i]}`);

		            }

		        }

		    }

		    return Queue;

		})();

		//深度优先搜索

		//广度优先搜索

		function Graph(){

			var vertices = []; //存储所有的顶点

			var adjList = {}; //存储所有顶点的相邻顶点

			this.addVertex = function(v){

				if(!adjList[v]){

					vertices.push(v);

					adjList[v] = [];

				}else{

					throw new Error("该顶点已经存在");

				}

			};

			var initializeColor = function(){

				var color = {};

				for(var i = 0; i < vertices.length; i++){

					color[vertices[i]] = 'white';

				}

				return color;

			}

			this.addEdge = function(v,w){

				if(adjList[v] && adjList[w]){

					adjList[v].push(w);

					adjList[w].push(v);

				}else{

					throw new Error("链接不存在的顶点");

				}

			};

			this.toString = function(){

				var s = '';

				for (var i=0; i<vertices.length; i++){ //{10}

				s += vertices[i] + ' -> ';

				var neighbors = adjList[vertices[i]]; //{11}

				for (var j=0; j<neighbors.length; j++){ //{12}

				s += neighbors[j] + ' ';

				}

				s += '\n'; //{13}

				}

				return s;

			};

			this.print = function(){

				console.log(this.toString());

			};

			//广度优先搜索,寻找每个点

			//搜索每个点的相邻点

			//1、初始化，所有的顶点状态为 white，即没有遍历到

			//2、通过该点，拿到相邻点的数组，遍历相邻点

			//3、如果相邻点是white，则变灰(表示发现该节点)。并加入队列

			//4、当相邻的都遍历完成,将自己变成黑色(表示已经探索完成该节点)，进入队列下一次的循环

			this.bfs = function(v,callback){

				var color = initializeColor();

				queue = new Queue();

				queue.enqueue(v);

				while(!queue.isEmpty()){

					var u = queue.dequeue();

					neighbors = adjList[u];

					color[u] = 'grey';

					for(var i = 0; i < neighbors.length; i++){

						var w = neighbors[i];

						if(color[w] === 'white'){

							color[w] = 'grey';

							queue.enqueue(w);

						}

					}

					color[u] = "black";

					if(callback){

						callback(u);

					}

				}

			};

			//广度优先算法，计算每个顶点的距离

			this.BFS = function(v){

				var color = initializeColor();

				queue = new Queue();

				queue.enqueue(v);

				d = [];    //距离列表

				pred = [];  //前溯点

				for (var i=0; i<vertices.length; i++){

					d[vertices[i]] = 0;

					pred[vertices[i]] = null;

				}

				while(!queue.isEmpty()){

					var u = queue.dequeue();

					neighbors = adjList[u];

					color[u] = 'grey';

					for(var i = 0; i < neighbors.length; i++){

						var w = neighbors[i];

						if(color[w] === 'white'){

							color[w] = 'grey';

							d[w] = d[u] + 1;

							pred[w] = u;

							queue.enqueue(w);

						}

					}

					color[u] = "black";

				}

				return {

					distances: d,

					predecessors: pred

				}

			}

			this.getPath = function(u){

				//打印最短路径

				//回溯之前的相邻点

				var  shortestPath = this.BFS(u);

				var fromVertex = vertices[0];

				for (var i=1; i<vertices.length; i++){ 

				var toVertex = vertices[i],

				path = [];

					for (var v=toVertex; v!== fromVertex;

						v=shortestPath.predecessors[v]) {

						path.push(v);

					}

					path.push(fromVertex);

					var s = path.join("-"); 

					console.log(s);

				}

			}

		  //深度优先算法

		  this.dfs = function(callback){

		  	var color = initializeColor();

		  	for(var i = 0; i < vertices.length; i++){

		  		if(color[vertices[i]] === 'white'){

					dfsVisit(vertices[i], color, callback);

		  		}

		  	}

		  }

		  function dfsVisit(u,color,callback){

		  	color[u] = 'grey';

		  	if(callback){

		  		callback(u);

		  	}

		  	var neighbors = adjList[u];

		  	for(var i = 0; i < neighbors.length; i++){

		  		var w = neighbors[i];

		  		if(color[w] === 'white'){

		  			dfsVisit(w,color,callback)

		  		}

		  	}

		  	color[u] = "black";

		  }

		 //深度搜索，发现时间（标记为灰色）和完成探索时间(标记为黑色)

		 //将发现时间倒序排列，即可得到拓扑图

		 var time = 0;

		 this.DFS = function(){

		 	var color = initializeColor(),

		 	d = [],

		 	f = [],

		 	p = [],

		 	time = 0;

		 	for(var i = 0; i < vertices.length; i++){

		 		f[vertices[i]] = 0;

		 		d[vertices[i]] = 0;

		 		p[vertices[i]] = null;

		 	}

		 	for(var i = 0; i < vertices.length; i++){

		 		if(color[vertices[i]] === 'white'){

		 			DFSVisit(vertices[i],color,d,f,p);

		 		}

		 	}

		 	return {

		 		discovery:d,

		 		finished:f,

		 		predecessors:p

		 	}

		 }

		 function DFSVisit(u,color,d,f,p){

		 	console.log("discovered" + u);

		 	color[u] = 'grey';

		 	d[u] = ++time;

		 	var neighbors = adjList[u];

		 	for(var i = 0; i < neighbors.length; i++){

		 		var w = neighbors[i];

		 		if(color[w] === 'white'){

		 			p[w] = u;

		 			DFSVisit(w,color,d,f,p);

		 		}

		 	}

		 	color[u] = 'block';

		 	f[u]  = ++time;

		 	console.log("explored"+u);

		 }

		}

		var graph = new Graph();

		var myVertices = ['A','B','C','D','E','F','G','H','I']; //{7}

		for (var i=0; i<myVertices.length; i++){ //{8}

		graph.addVertex(myVertices[i]);

		}

		graph.addEdge('A', 'B'); //{9}

		graph.addEdge('A', 'C');

		graph.addEdge('A', 'D');

		graph.addEdge('C', 'D');

		graph.addEdge('C', 'G');

		graph.addEdge('D', 'G');

		graph.addEdge('D', 'H');

		graph.addEdge('B', 'E');

		graph.addEdge('B', 'F');

		graph.addEdge('E', 'I');

		/*

		graph.bfs("A",function(cnode){

			console.log(cnode);

		})

		console.log(graph.BFS("A"));

		graph.getPath('A');

		graph.dfs(function(cnode){

			console.log(cnode);

		});*/

		console.log(graph.DFS());

		/*

		 如果要计算加权图中的最短路径(例如城市之间最短距离)广度优先搜索未必合适。

		 *  Dijkstra算法解决了单源最短路径问题。 Bellman-Ford算法解决了边权值为负的

单源最短路径问题。 A*搜索算法解决了求仅一对顶点间的最短路径问题，它用经验法则来加速搜

索过程。 Floyd-Warshall算法解决了求所有顶点对间的最短路径这一问题。

		 *

		 * */