w3ctech

无厘头 Graph

前言

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

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

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

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

V => 表示顶点

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

那么用数学来表示就是:G=<V, E>

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

如何表示图呢?

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

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

图

图的结构确定过后,就可以做出表的结构了,这里我没有用方向,因为我理解的图是一个不能简单表示的,理解成坐标系更好理解一点。分为: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

w3ctech微信

扫码关注w3ctech微信公众号

共收到0条回复

只有w3ctech成员才能发表和回复。
登录 或者 注册 后发表或回复!