构建图：
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=>B
g.bfs('A', function(e) {console.log(e)}); //A B C D E F
g.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 A
zuiduan('A','E') //A-B-F