专栏首页原创分享js实现图的构造和遍历

js实现图的构造和遍历

class Graph {
    constructor() {
        this.v = {}; 
        this.vLen = 0;
        this.eLen = 0;
    }

    addEdge(from, to) {
        if (!this.v[from.id]) {
            this.v[from.id] = {};
            this.v[from.id]['node'] = from;
            this.v[from.id]['edge'] = [];
            this.vLen++;
        }
        if (!this.v[to.id]) {
            this.v[to.id] = {};
            this.v[to.id]['node'] = to;
            this.v[to.id]['edge'] = [];
            this.vLen++;
        }
        this.v[from.id]['edge'].push(to);
        this.v[to.id]['edge'].push(from);
        this.eLen++;
    }
}

class Operation {
    constructor(graph) {
        this.graph = graph;
        this.marked = {};
    }
    count(node) {
        if (node !== void 0) {
            if (this.graph['v'][node.id]) {
                return this.graph['v'][node.id]['edge'].length;
            } else {
                return 0;
            }
        } else {
            for (var key in this.graph['v']) {
                console.log(this.graph['v'][key]['edge'].length)
            }
        }
    },

    traversalDFS(node) {

        if (this.marked[node.id]) {
            return;
        }

        console.log(node.id);
        this.marked[node.id] = true;
        var v = this.graph['v'][node.id]['edge'];
        for (var i = 0; i < v.length; i++) {
            if (!this.marked[v[i].id]) {
                this.traversal(v[i])
            }
        }
    },

    traversalBFS(node) {
        var i = 0;
        var queue = [node];
        var point;
        var v;
        var marked = {};
        while(point = queue.shift()) {

            if (marked[point.id]) {
                continue;
            } else {
                console.log(point.id);
                marked[point.id] = true;
            }
            v = this.graph['v'][point.id]['edge'];
            queue = queue.concat(v);
        }
    }
}

var graph = new Graph();
for(var i = 0; i < 5; i++) {
    var from = {id: i};
    var to = {id: i + 1};
    graph.addEdge(from, to);
}
graph.addEdge({id: 2}, {id: 5});
graph.addEdge({id: 1}, {id: 4});

var op = new Operation(graph)

op.traversalDFS(graph, {id:4})
op.traversalBFS(graph, {id:1})

本文分享自微信公众号 - 编程杂技(theanarkh)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 通用的组件请求管理器,解决异步请求中的后发先到的问题

    1.每当需要取消之前发出的请求时,需要调用clearRequestId方法。 2.在优化版本中,显式定义了两种取消请求的方法,clearFormerReque...

    theanarkh
  • express的router.js源码分析(router/index.js)

    router.js的代码其实是router/index.js,里面的代码是express的路由的核心和入口。下面我们看一下重要的代码。

    theanarkh
  • 用js模拟一下操作系统

    theanarkh
  • 获取jqGrid中选择的行的数据

    var id=$(‘#gridTable’).jqGrid(‘getGridParam’,'selrow’);

    ydymz
  • THINKPHP 中关联查询(多表查询)

    THINKPHP 中关联查询(多表查询)可以使用 table() 方法或和join方法,请看示例:

    公众号php_pachong
  • select from update row的实现

    DTCC大会上,阿里江疑的演讲中提到一个:select from update hot row;

    bisal
  • TP踩过的坑【批量删除,(不涉及子栏目的批量删除)】

    简单、
  • [ASP.NET Core 3框架揭秘] 跨平台开发体验: Linux

    如果想体验Linux环境下开发.NET Core应用,我们有多种选择。一种就是在一台物理机上安装原生的Linux,我们可以根据自身的喜好选择某种Linux Di...

    蒋金楠
  • jquery怎么给循环出来的列表(类似于text框)取值和赋值

    场景描述:这样的我在项目的时候遇到了一个很常见的问题,但是一直没有解决,最后在朋友的帮助下解决了,所以简单的将这个代码和解决的过程描述一下,给以后你们遇到类...

    何处锦绣不灰堆
  • mybatis文件映射之关联查询初探(一)

    其中tbl_employee表中的d_id关联tbl_department表中的id字段

    绝命生

扫码关注云+社区

领取腾讯云代金券