Open lznbuild opened 4 years ago
可以用邻接矩阵表示,非常浪费内存,添加和删除点很麻烦 也可用邻接表
var Graph = function(){ // 存储顶点 var vertices = []; // 边 var adjList = {} // 添加顶点 var addVertex = function(v){ vertices.push(v) adjList[v] = []; } // 添加边 var addEdge = function(a,b){ adjList[a].push(b) adjList[b].push(a) } // white 未发现的节点 gray已发现 black已探索 var initColor=function(){ var color = {}; for(var i=0;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 = adList[now]; for(var i=0;i<bian.length;i++){ var w = bian[i]; if(color[w] === 'white'){ // 未发现的全部入列,并且标识为已发现 color[w] = 'gray'; queue.enqueue(w) } } color[now] = 'black'; if(callback){ callback(now) } } } // 使用广度优先查找最短路径,先建立关系 // d 距离 //pred 回溯点 this.BFS = function (v,callback){ // 遍历的广度优先 var color = initColor(); var queue = new Queue(); queue.enqueue(v); var d = {} var pred = {} for(let i=0;i<vertices.length;i++){ d[vertices[i]] = 0; //初始化 pred[vertices[i]]= null } while(!queue.isEmpty()){ var now = queue.dequeue; var bian = adList[now]; for(var i=0;i<bian.length;i++){ var w = bian[i]; if(color[w] === 'white'){ // 未发现的全部入列,并且标识为已发现 color[w] = 'gray'; //设置回溯点 pred[w] = now d[w]=d[now]+1 queue.enqueue(w) } } color[now] = 'black'; if(callback){ callback(now) } } return { d, pred } } var dfsVisite = function(u,color,callback){ color[u] = 'gray' var n = adList[u] for(var i=0;i<n.length;i++){ var w = n[i]; if(color[w]) == 'while'){ dfsVisite(w,color,callback) } } color[u] = 'block'; if(callback){ callback(u) } } // 遍历的深度优先 ths.dfs = function(v,callback){ var color = initColor(); //初始化 dfsVisite(v, color, callback) } } // 使用 var s=g.BFS('A'); //广度优先算法查找最短路径 var zuiduan = function(form,to){ var v = to; 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) return str } // 图的遍历:广度优先(队列) 深度优先(递归,栈)
图
可以用邻接矩阵表示,非常浪费内存,添加和删除点很麻烦 也可用邻接表