无厘头 Graph

jayzou 发布于2019-08-22 10:47 / 3078人阅读

摘要：老孙到此一游对于深度遍历，是将图按一个固定方向，纵向的结果，所以是一个递归的结构。老孙到此一游对于广度遍历，是将图按一个固定方向，横向的结果，所以是一个链式进出的关系，这里是用队列，在中做队列这种先进先出比较简单。

前言

今天晚上无意翻到一个图的文章，查了一下感觉网上实现和其他都好复杂，所以自己按理解搞了一下，不知道是我实现是不是错了...感觉还好～进入正题，先还是来点理论知识，不过大多是自己的想法，不一定都对，可以纠正。内容来源来自《JavaScript 数据结构和算法》。

图

图是一种数学模型，和数学挂勾一般都会比较复杂，所以形象的理解成最简单的模型，点-线 模型。其实最简单的是 1 个点的模型，涉及 2 个点还好，3 个点过后模型就会作出相应的改变。

这里用简单的语言来说图中的二元关系，不过还是先假设一点数学符号：

G => 表示所有的顶点集合

V => 表示顶点

E => 表示边，抽象意义上是无向边

那么用数学来表示就是：G=

其实根本不用理解数学的模型，我这里理解是只需要知道这是一个点-线模型就可以了。

如何表示图呢？

这里有两种表示方法：表和矩阵，其间都是邻接关系

这里我有一个测试图，在网上弄的，虽然是无向图，其实在我们代码中，肯定是有向的，是入口的问题：

图的结构确定过后，就可以做出表的结构了，这里我没有用方向，因为我理解的图是一个不能简单表示的，理解成坐标系更好理解一点。分为：x, y 轴的方式。其中，x0 表示开始，后面表示相邻的点，按顺时针排列（不一定按这个顺序）。

代码中的图

在代码中表示，没有图形那么直观，所以需要映射成代码模型，这里简单实现一下，但是不具备很多功能。

假设：

class G => 一个图的类，包括图的定义和常用遍历方法

this.V => 表示点集合的个数，但是这里我舍弃了 0 的位置

this.T => 我按数据库表的方式理解命名的，关系的集合

this.E => 边的个数

this.visited => 访问过的 bool 集合，其实就是标记

this.defined => 工具小函数，是否定义过，与图无关

所以最后有关的符号有：

G、V、T、E

是不是感觉一下子变简单了，不过程序的抽象有一个上层，那就是类。
然后我这里按计算机的方式，定义了输入、输出函数：input、output

class G {
    constructor(V) {
        this.V = V;
        this.T = [];
        this.E = 0;
        this.visited = [];

        for (let v = 0; v < this.V; ++v) {
            this.T[v] = [];
            this.T[v].push(-1);
        }

        this.defined = s => s !== void 0;
    }
    input(v, w) {
        this.T[v].push(w);
        this.T[w].push(v);

        this.E++;

        return this;
    }
    output() {
        console.table(this.T);
    }
}

然后能够看出，其实边是由点的连接组成的，刚好符合数学的定义，并且与相邻有相关性。

那么，实现了结构，还应该有其他作用，那么接下来看一下遍历算法：深度遍历（DFS）和广度遍历（BFS）。准确来说应该是优先采用什么策略的遍历方式。其实我这里的实现感觉...不好，和树关系大了点，不过树的大集合就能够上升到图。

dfs(v) {
    this.visited[v] = true;

    if (this.defined( this.T[v] )) {
        console.log("老孙到此一游：" + v);
    }

    this.T[v].forEach(t => {
        if (t !== -1 && !this.visited[t]) {
            this.dfs(t);
        }
    });
}

对于深度遍历，是将图按一个固定方向，纵向的结果，所以是一个递归的结构。

bfs(node) {
    this.visited[node] = true;

    var queue = [];
    queue.push(node);
    while(queue.length > 0) {
        var v = queue.shift();
        if(this.defined( this.T[v] )) {
            console.log("老孙到此一游：" + v);
        }

        this.T[v].forEach(t => {
            if(t !== -1 && !this.visited[t]) {
                this.visited[t] = true;
                queue.push(t);
            }
        });
    }
}

对于广度遍历，是将图按一个固定方向，横向的结果，所以是一个链式进出的关系，这里是用队列，在 JS 中做队列这种先进先出比较简单。

// 测试代码
var v = [1, 2, 3, 4, 5];
let g = new G( v.length + 1 );
g.input(1, 2).input(1, 5)
    .input(2, 4).input(2, 5).input(2, 3)
    .input(3, 4)
    .input(4, 5)
    .output();
g.dfs(1);
console.log("------------");
// 让它失忆一下
g.visited = [];
g.bfs(1);

……-_-# 简单玩一下，睡觉了 zZZ

云服务器 GPU云服务器无厘头 graph graph编程语言

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

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

彻底理解z-index，看完还是只会无厘头的设置9999你打我~~~~

摘要：如果同级父元素不是层叠上下文元素就不需要看父元素的眼色了文章到这里就结束了，希望看完这篇文章的同学可以彻底理解。今天写代码用antd-mobile的checkbox时候，想在内容文本后面添加一个icon，并且需要对这个icon绑定事件，发现绑定之后怎么也点不中，调试发现原来被层层嵌套的dom元素盖住了，肯定是z-index在作祟。可是按照我之前对z-index的了解（自信满满）却怎么...

bladefury 2019-08-02 16:16 评论0 收藏0
彻底理解z-index，看完还是只会无厘头的设置9999你打我~~~~

摘要：如果同级父元素不是层叠上下文元素就不需要看父元素的眼色了文章到这里就结束了，希望看完这篇文章的同学可以彻底理解。今天写代码用antd-mobile的checkbox时候，想在内容文本后面添加一个icon，并且需要对这个icon绑定事件，发现绑定之后怎么也点不中，调试发现原来被层层嵌套的dom元素盖住了，肯定是z-index在作祟。可是按照我之前对z-index的了解（自信满满）却怎么...

RobinTang 2019-08-30 10:51 评论0 收藏0
js下探究 let, var 之于闭包

摘要：问题在说闭包，一定会牵涉到作用域。这也是闭包的属性的，能够记录下内部函数引用外部的值。因为都是全局变量，所以循环也就是不断值覆盖，闭包并不会记录在循环时的值，只会记录闭包变量。闭包时记录的除了闭包变量还有块级作用域变量最后来看看这个输出什么 js 是非常灵活的语言，写起来真是* 不过现在有了typescript，写起来舒服多了。问题在说js闭包，一定会牵涉到作用域。而一般在区别 v...

BLUE 2019-08-26 12:02 评论0 收藏0
微信小程序项目总结（一）

摘要：前言微信小程序的开发，我应该算是赶上了第一波，所以，自然是一路踩坑而来。注以下标题是按照微信开发工具上的选项进行划分的。不过，除此之外，它还会产生另外一个副作用，就是可能连小程序本身上的请求都请求不了了。 -- KChris 2017.3.16 (=^.^=) 前言微信小程序的开发，我应该算是赶上了第一波，所以，自然是一路踩坑而来 =。=一月九日，小程序正式上线，早早地就到公司开始改b...

whatsns 2019-08-20 15:09 评论0 收藏0