javascript实现的图数据结构的广度优先 搜索(Breadth-First Search,BFS)和深度优先搜索(Depth-First Search,DFS)

简介: 最后一例,搞得快。三天之内走了一次。。 下一步,面象对像的javascript编程。 function Dictionary(){ var items = {}; this.

最后一例,搞得快。三天之内走了一次。。

下一步,面象对像的javascript编程。

function Dictionary(){
    var items = {};

    this.has = function (key) {
        return key in items;
    };

    this.set = function(key, value){
        items[key] = value;
    };

    this.remove = function(key){
        if (this.has(key)){
            delete items[key];
            return true;
        }
        return false;
    };

    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    };

    this.values = function(){
        var values = [];
        for(var k in items){
            if (this.has(k)) {
                values.push(items[k]);
            }
        }
        return values;
    };

    this.clear = function(){
        items = {};
    };

    this.size = function(){
        var count = 0;
        for (var prop in items){
            if(items.hasOwnProperty(prop)){
                ++count;
            }
        }
        return count;
    };

    this.getItems = function(){
        return items;
    };
}

function Queue() {
    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.clear = function(){
        items = [];
    }

    this.size = function(){
        return items.length;
    }

    this.print = function(){
        console.log(items.toString());
    }
}

function Graph() {
    var vertices = [];
    var adjList = new Dictionary();

    var initializeColor = function(){
        var color = [];
        for (var i=0; i<vertices.length; i++){
            color[vertices[i]] = 'white'; //{1}
        }
        return color;
    };

    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 = function(v, callback){
        var color = initializeColor(), //{2}
            queue = new Queue(); //{3}
        queue.enqueue(v); //{4}
        while (!queue.isEmpty()){ //{5}
            var u = queue.dequeue(), //{6}
            neighbors = adjList.get(u); //{7}
            color[u] = 'grey'; // {8}
            for (var i=0; i<neighbors.length; i++){ // {9}
                var w = neighbors[i]; // {10}
                if (color[w] === 'white'){ // {11}
                    color[w] = 'grey'; // {12}
                    queue.enqueue(w); // {13}
                }
            }
            color[u] = 'black'; // {14}
            if (callback) { // {15}
                callback(u);
            }
        }
    };

    this.dfs = function(callback){
        var color = initializeColor(); //{1}
        for (var i=0; i<vertices.length; i++){ //{2}
            if (color[vertices[i]] === 'white'){ //{3}
                dfsVisit(vertices[i], color, callback); //{4}
            }
        }
    };
    var dfsVisit = function(u, color, callback){
        color[u] = 'grey'; //{5}
        if (callback) { //{6}
            callback(u);
        }
        var neighbors = adjList.get(u); //{7}
        for (var i=0; i<neighbors.length; i++){ //{8}
            var w = neighbors[i]; //{9}
            if (color[w] === 'white'){ //{10}
                dfsVisit(w, color, callback); //{11}
            }
        }
        color[u] = 'black'; //{12}
    };

    this.toString = function(){
        var s = '';
        for (var i=0; i<vertices.length; i++){ //{10}
            s += vertices[i] + ' -> ';
            var neighbors = adjList.get(vertices[i]); //{11}
            for (var j=0; j<neighbors.length; j++){ //{12}
                s += neighbors[j] + ' ';
            }
            s += '\n'; //{13}
        }
        return s;
    };
}

var graph = new Graph();
var myVertices = ['A','B','C','D','E','F','G','H','I'];
for (var i=0; i<myVertices.length; i++){
    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');

console.log(graph.toString());

function printNode(value){ //{16}
    console.log('Visited vertex: ' + value); //{17}
}
graph.bfs(myVertices[0], printNode); //{18}
graph.dfs(printNode);

目录
相关文章
|
2月前
|
JavaScript 前端开发
js实现数据的双向绑定
js实现数据的双向绑定
113 59
|
2月前
|
JavaScript 算法 前端开发
采招网JS逆向:基于AES解密网络数据
采招网JS逆向:基于AES解密网络数据
43 0
|
2天前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
19天前
|
JavaScript 前端开发 安全
js逆向实战之烯牛数据请求参数加密和返回数据解密
【9月更文挑战第20天】在JavaScript逆向工程中,处理烯牛数据的请求参数加密和返回数据解密颇具挑战。本文详细分析了这一过程,包括网络请求监测、代码分析、加密算法推测及解密逻辑研究,并提供了实战步骤,如确定加密入口点、逆向分析算法及模拟加密解密过程。此外,还强调了法律合规性和安全性的重要性,帮助读者合法且安全地进行逆向工程。
66 11
|
1天前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
在数据结构的广袤领域中,图是一种强大而复杂的结构,而深度优先搜索(DFS)和广度优先搜索(BFS)则是遍历图的两把利剑。Python 以其简洁和强大的特性,为我们提供了实现和运用这两种算法的便捷途径。
13 0
|
2天前
|
数据采集 JavaScript 前端开发
JavaScript中通过array.filter()实现数组的数据筛选、数据清洗和链式调用,JS中数组过滤器的使用详解(附实际应用代码)
JavaScript中通过array.filter()实现数组的数据筛选、数据清洗和链式调用,JS中数组过滤器的使用详解(附实际应用代码)
|
14天前
|
JSON JavaScript 前端开发
6-19|Python数据传到JS的方法
6-19|Python数据传到JS的方法
|
2月前
|
JavaScript 数据安全/隐私保护 Python
网易云音乐搜索接口JS逆向: Params、encSecKey加密和AES实战
网易云音乐搜索接口JS逆向: Params、encSecKey加密和AES实战
57 4
|
2月前
|
JSON JavaScript 数据格式
js实现更新数据
js实现更新数据
48 1
|
2月前
|
前端开发 JavaScript 安全
JavaScript——数字超过精度导致数据有误
JavaScript——数字超过精度导致数据有误
34 2