学习JavaScript数据结构与算法第9章图

构建图：

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