《学习JavaScript数据结构与算法》（第9章）（图）

bitkylin 发布于2019-08-26 10:38 / 1966人阅读

摘要：构建图添加顶点用数组存储图中所有顶点的名字添加边用对象的形式存储每个顶点包含的边功能打印广度优先遍历采用队列数据结构广度优先遍历采用队列数据结构未发现的全部入列，并且标识为已发现深度优先遍历初始化颜色构建函数基于广度优先的最短路径生成算法设

构建图：

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() {
        let s = "
";
        for(let i=0; i";
            let bian = adjList[dingdian];
            for(let j=0; j
2、广度优先遍历（采用队列数据结构）
let initColor = function() {
       let color = [];
       for(let i=1; i
3、深度优先遍历
 this.dfs = function(v,callback) {
        let color = initColor();   //初始化颜色
        dfsVisite(v,color,callback);
    }

    let dfsVisite = function(u,color,callback) {
        color[u] = "grey";
        let n = adjList[u];
        for(let i=0; i
构建函数：
1、基于广度优先的最短路径生成算法
let  zuiduan = function(from,to){
    let v  = to; //设置当前点
    let s = g.BFS(from);
    let path = new Stack();
    while(v !== from) {
        path.push(v);
        v = s.pred[v];
    }
    path.push(v);
    let str = "";
    while(!path.isEmpty()) {
        str += path.pop() + "-";
    }
    str = str.slice(0,str.length-1);
    console.log(str);
}
全部整体代码
//栈
let 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());
    }
};

//队列
let Queue= function() {
    let 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;
    };
};

//图
let Graph = function() {
    //顶点(用数组存储图中所有顶点的名字)
    let vertices = [];
    //边（用对象的形式存储每个顶点包含的边）
    let 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() {
        let s = "
";
        for(let i=0; i";
            let bian = adjList[dingdian];
            for(let j=0; j
结果测试
let 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

云服务器 GPU云服务器明解c语言第9章 js数据结构与算法第2 js数据结构与算法+第2 javascript基础教程第9版

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106512.html

ApacheCN 人工智能知识树 v1.0

摘要：贡献者飞龙版本最近总是有人问我，把这些资料看完一遍要用多长时间，如果你一本书一本书看的话，的确要用很长时间。为了方便大家，我就把每本书的章节拆开，再按照知识点合并，手动整理了这个知识树。 Special Sponsors showImg(https://segmentfault.com/img/remote/1460000018907426?w=1760&h=200); 贡献者：飞龙版...

刘厚水 2019-06-26 19:00 评论0 收藏0
《学习JavaScript数据结构与算法》（第8章）（树）

摘要：先序遍历的一种应用是打印一个结构化的文档。方法的实现如下中序遍历中序遍历是一种以上行顺序访问所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。 1、二叉搜索树(两个条件)：（1）二叉树中的节点最多只有两个子节点：一个是左侧节点，另一个是右侧子节点；（2）只允许在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的...

30e8336b8229 2019-08-26 10:36 评论0 收藏0
《学习JavaScript数据结构与算法》（第8章）（平衡二叉树代码实现）

摘要：平衡二叉树代码实现根节点插入节点树为空树不为空比较小于往左走大于往右走空树树非空自平衡树插入新节点向左走向左子树拆入新节点，且节点的值小于其左子节点时，应该进行旋转。平衡二叉树JS代码实现 var Tree = function() { var Node = function(value) { this.value = value; this....

isLishude 2019-08-26 10:37 评论0 收藏0
重读《学习JavaScript数据结构与算法-第三版》- 第3章数组（一）

摘要：此处应该有掌声前言读学习数据结构与算法第章数组，本节将为各位小伙伴分享数组的相关知识概念创建方式常见方法以及数组的新功能。数组数组是最简单的内存数据结构，用于存储一系列同一种数据类型的值。定场诗大将生来胆气豪，腰横秋水雁翎刀。风吹鼍鼓山河动，电闪旌旗日月高。天上麒麟原有种，穴中蝼蚁岂能逃。太平待诏归来日，朕与先生解战袍。此处应该有掌声... 前言读《学习JavaScrip...

iKcamp 2019-08-26 10:46 评论0 收藏0
翻译连载 | 第 9 章：递归（上）－《JavaScript轻量级函数式编程》 |《你不知道的JS》

摘要：一旦我们满足了基本条件值为，我们将不再调用递归函数，只是有效地执行了。递归深谙函数式编程之精髓，最被广泛引证的原因是，在调用栈中，递归把大部分显式状态跟踪换为了隐式状态。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者关于译者：这是一个流淌着沪江血液的纯粹工程：认真，是 HTML 最坚实的梁柱；...

MasonEast 2019-08-22 11:11 评论0 收藏0