构建图：
1、添加顶点：用数组存储图中所有顶点的名字
this.addVertex = function(v) { vertices.push(v); adjList[v] = []; }2、添加边 ：用对象的形式存储每个顶点包含的边
this.addEdge = function(a,b) { adjList[a].push(b); adjList[b].push(a); }功能：
1、打印
this.print= function() { var s = '\n'; for(var i=0; i<vertices.length; i++) { var dingdian = vertices[i]; s += dingdian + '=>'; var bian = adjList[dingdian]; for(var j=0; j<bian.length; j++) { s += bian[j]; } s += '\n'; } console.log(s); } 2、广度优先遍历（采用队列数据结构）
var initColor = function() { var color = []; for(var i=1; i<vertices.length; i++) { color[vertices[i]] = 'white'; } return color; }; //广度优先遍历（采用队列数据结构） this.bfs = function(v,callback) { var color = initColor(); var queue = new Queue; queue.enqueue(v); while(!queue.isEmpty()) { var now = queue.dequeue(); var bian = adjList[now]; for(var i=0; i<bian.length; i++) { var w = bian[i]; if(color[w] === 'white') { //未发现的全部入列，并且标识为已发现 color[w] = 'grey'; queue.enqueue(w); } } color[now] = 'black'; if(callback) { callback(now); } } };3、深度优先遍历
this.dfs = function(v,callback) { var color = initColor(); //初始化颜色 dfsVisite(v,color,callback); } var dfsVisite = function(u,color,callback) { color[u] = 'grey'; var n = adjList[u]; for(var i=0; i<n.length; i++) { var w = n[i]; if(color[w] == 'white') { dfsVisite(w,color,callback); } } color[u] = 'black'; if(callback) { callback(u); } };构建函数：
1、基于广度优先的最短路径生成算法
var zuiduan = function(from,to){ var v = to; //设置当前点 var s = g.BFS(from); var path = new Stack(); while(v !== from) { path.push(v); v = s.pred[v]; } path.push(v); var str = ''; while(!path.isEmpty()) { str += path.pop() + '-'; } str = str.slice(0,str.length-1); console.log(str);}全部整体代码
//栈var Stack = function() { let items = []; //添加元素 this.push = function(element) { items.push(element); }; //删除元素 this.pop = function() { return items.pop(); }; //查看栈顶元素 this.peek = function() { return items[items.lenght -1]; }; //检查栈是否为空 this.isEmpty = function() { return items.length == 0; } //栈的长度 this.size = function() { return items.length; } //清空栈 this.clear = function() { items = []; } //打印栈元素 this.print = function() { console.log(items.toString()); }};//队列var Queue= function() { var items = []; //入队 this.enqueue = function(element) { items.push(element); }; //出队 this.dequeue = function() { return items.shift(); }; //查看队列头 this.front = function() { return items[0]; }; //检查队列是否为空 this.isEmpty = function() { return items.length === 0; }; //队列大小 this.size = function() { return items.length; };};//图var Graph = function() { //顶点(用数组存储图中所有顶点的名字) var vertices = []; //边（用对象的形式存储每个顶点包含的边） var adjList = {}; //1、添加顶点 this.addVertex = function(v) { vertices.push(v); adjList[v] = []; } //2、添加边 this.addEdge = function(a,b) { adjList[a].push(b); adjList[b].push(a); } //打印 this.print= function() { var s = '\n'; for(var i=0; i<vertices.length; i++) { var dingdian = vertices[i]; s += dingdian + '=>'; var bian = adjList[dingdian]; for(var j=0; j<bian.length; j++) { s += bian[j]; } s += '\n'; } console.log(s); } /* 广度优先遍历： white 未发现 grey 已发现未探索 black 已探索 */ //初始化颜色 var initColor = function() { var color = []; for(var i=1; i<vertices.length; i++) { color[vertices[i]] = 'white'; } return color; }; //广度优先遍历（采用队列数据结构） this.bfs = function(v,callback) { var color = initColor(); var queue = new Queue; queue.enqueue(v); while(!queue.isEmpty()) { var now = queue.dequeue(); var bian = adjList[now]; for(var i=0; i<bian.length; i++) { var w = bian[i]; if(color[w] === 'white') { //未发现的全部入列，并且标识为已发现 color[w] = 'grey'; queue.enqueue(w); } } color[now] = 'black'; if(callback) { callback(now); } } }; //广度优先算法（d:距离 prev：回溯点） this.BFS = function(v) { var color = initColor(); var queue = new Queue; queue.enqueue(v); //初始化 var d = {}; var pred = {}; for(var i=0; i<vertices.length; i++) { d[vertices[i]] = 0; pred[vertices[i]] = null; } while(!queue.isEmpty()) { var now = queue.dequeue(); var bian = adjList[now]; for(var i=0; i<bian.length; i++) { var w = bian[i]; if(color[w] === 'white') { color[w] = 'grey';//未发现的全部入列，并且标识为已发现 //设置回溯点 pred[w] = now; d[w] = d[now] + 1; queue.enqueue(w); } } color[now] = 'black'; } return { pred : pred, d : d }; }; //深度优先算法 this.dfs = function(v,callback) { var color = initColor(); //初始化颜色 dfsVisite(v,color,callback); } var dfsVisite = function(u,color,callback) { color[u] = 'grey'; var n = adjList[u]; for(var i=0; i<n.length; i++) { var w = n[i]; if(color[w] == 'white') { dfsVisite(w,color,callback); } } color[u] = 'black'; if(callback) { callback(u); } };};//广度优先算法解决最短路径问题 （保证每个点的回溯点是最短的)var zuiduan = function(from,to){ var v = to; //设置当前点 var s = g.BFS(from); var path = new Stack(); while(v !== from) { path.push(v); v = s.pred[v]; } path.push(v); var str = ''; while(!path.isEmpty()) { str += path.pop() + '-'; } str = str.slice(0,str.length-1); console.log(str);}结果测试
var g =new Graph;g.addVertex('A');g.addVertex('B');g.addVertex('C');g.addVertex('D');g.addVertex('E');g.addVertex('F');g.addEdge('A','B');g.addEdge('A','C');g.addEdge('A','D');g.addEdge('C','D');g.addEdge('B','E');g.addEdge('F','B');g.print(); //A=>BCD B=>AEF C=>AD D=>AC E=>B F=>Bg.bfs('A', function(e) {console.log(e)}); //A B C D E Fg.BFS('A'); //d:{A:0, B:1, C:1, D:1, E:2} pred:{A:null, B:"A", C:"A", D:"A", E:"B"}g.dfs('A',function(e){console.log(e);}); //E F B D C Azuiduan('A','E') //A-B-F