上次在最后提到vue-router路由匹配明显不是深度优先搜索,然后需要看vue-router的源码研究其到底是用的何种搜索算法。vue-router源码并不多,看完也不是什么难事,可vue.js源码多呀,vue2.0八千多行,一时半会儿看不完!
还是接着巩固算法吧,这次就记录一下图的基本搜索算法,参考的书籍和之前一样。
function Graph() { var vertices = []; var adjList = new Dictionary(); this.addVertex = function (v) { vertices.push(v); adjList.set(v, []); }; this.addEdge = function (v, w) { adjList.get(v).push(w); adjList.get(w).push(v); }; this.bfs = bfs; this.dfs = dfs; } function initializeColor() { var color = []; for (var i = 0; i < vertices.length; i++) { color[vertices[i]] = 'white'; } return color; } function bfs(v, callback) { var color = initializeColor(); queue = new Queue(); queue.enqueue(v); while (!queue.inEmpty()) { var u = queue.dequeue(); var neighbors = adjList.get(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); } } } function dfs(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.get(u); for (var i = 0; i < neighbors.length; i++) { var w = neighbors[i]; if (color[w] === 'white') { dfsVisit(w, color, callback); } } color[u] = 'black'; }
Graph构造函数定义了一个图的数据结构,内部有vertices和adjList两个私有变量以及4个实例方法,Dictionary是一个字典类,这里就不写其实现了,bfs是广度优先算法,内部用队列实现,dfs是深度优先搜索,内部用类似栈的递归调用实现。
每一个顶点会有白、灰、黑三种颜色,分别表示未访问过,访问过但未探索和访问过和且探索完。