图

2021-11-09

图数据结构的封装

一. 什么是图?

在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。例如:

二. 图的一些术语

无向边：若顶点 x 和 y 之间的边没有方向，则称该边为无向边(x, y)，(x, y) 与 (y,x) 意义相同，表示 x 和 y 之间有连接。

无向图：若图中任意两个顶点之间的边均是无向边，则称该图为无向图（如上图G1，G2）。

有向边：若顶点 x 和 y 之间的边有方向，则称该边为有向边<x, y>，<x, y> 与 <y, x> 意义不同，表示从 x 连接到 y，x 称为尾，y 称为头。

有向图：若图中任意两个顶点之间的边均是有向边，则称该图为有向图（如上图G3，G4）。

在图中的两个重要关系是邻接和关联。

邻接：是两个顶点之间的一种关系。如果图包含（u,v），则称顶点v与顶点u邻接。在无向图中，这也暗示了顶点u也与顶点v邻接。换句话说，在无向图中邻接关系是对称的。

关联：是指顶点和边之间的关系。在有向图中，边（u,v）从顶点u开始关联到v，或者相反，从顶点v开始关联到u。在无向图中，边(u,v)与顶点u和v相关联。

完全图：每个顶点都与其他顶点相邻接的图。

路径：依次遍历顶点序列之间的边所形成的轨迹。没有重复顶点的路径称为简单路径。路径的长度是路径上的边或弧的数目。

环是指路径包含相同的顶点两次或两次以上。也就是说，在有向图的一条路径中，如果从某顶点出发，最后能够返回该顶点，则该路径是环。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单环或简单回路。

连通性是图中另一个重要的概念。对于无向图而言，如果它的每个顶点都能通过某条路径到达其他顶点，那么我们称它为联通的。如果该条件在有向图中同样成立，则称该图是强连通。尽管无向图可能不是连通的，但它扔然可能包含连通的部分，这部分分支为连通分支。如果有向图中只有部分是强连通的，则该部分称为强连通分支。

某些特定的顶点对于保护图或连通分支的连通性有特殊的重要意义。如果移除某个顶点将使得图或某分支失去连通性，则称该顶点为关结点。

三. javascript封装一个图

首先需要一个数据结构来储存图中的每一个顶点,可以是数数组,可以是链表等
还需要一个数据结构来储存对应的边,可以是字典也可以是集合
这里我用数组和js内置对象Map来简单的实现一个图的数据结构

代码:

function Graph() {
    this.point = [],
        this.edge = new Map()

    // 添加顶点
    Graph.prototype.addPoint = function (v) {
        this.point.push(v)
        this.edge.set(v, [])
    }

    //添加边
    Graph.prototype.addEdge = function (v1, v2) {
        //由于封装的是无向图 所以需要在两个顶点的边中都互相添加
        this.edge.get(v1).push(v2)
        this.edge.get(v2).push(v1)
    }

    //toString方法
    Graph.prototype.toString = function () {
        // 储存最终的字符串
        let resultstr = ''
        // 
        console.log(this.point, this.edge);
        for (let i = 0; i < this.point.length; i++) {
            let pointstr = this.point[i] + '-->'
            for (let j = 0; j < this.edge.get(this.point[i]).length; j++) {
                pointstr += this.edge.get(this.point[i])[j] + " "
            }
            resultstr += pointstr + '\n'
        }
        console.log(resultstr);
        return resultstr
    }
}
// 新建图的石磊
var grap = new Graph()
// 给图添加三个顶点
grap.addPoint('A')
grap.addPoint('B')
grap.addPoint('C')
// 添加A->B的边 添加 A->C的边 
grap.addEdge('A', "B")
grap.addEdge('A', "C")
grap.toString()
// 打印结果

//A-->B C 
//B-->A 
//C-->A

此时数据结果是这个样:

后续还用图的遍历方法…..明天在写哦

来喽来喽!

三.图的遍历

3.1 广度优先遍历:

 // 初始化图的状态 用三种颜色表示图中顶点的状态
Graph.prototype.initColor = function () {
    let colors = []
    for (let i = 0; i < this.point.length; i++) {
        colors[this.point[i]] = 'white'
    }
    return colors
}

// 实现图的广度优先遍历
Graph.prototype.BFC = function (initV, handler) {
    // 1.初始化颜色  // color: [A: 'white', B: 'white', C: 'white']
    let colors = this.initColor()

    // 2.创建一个队列辅助
    let queue = new Queue()

    //3 把第一个顶点入队
    queue.enqueue(initV)

    // 4.开始循环遍历queue
    while (!queue.isEmpty()) {
        // 4.1 从队列中取出一个顶点
        var v = queue.dequeue();

        // 4.2 获取和顶点相连的其他顶点
        var vList = this.edge.get(v);
        // 4.3 将v的颜色设置成灰色
        colors[v] = 'gray';

        // 4.4 遍历所有的顶点，并且加入到队列中
        for (var i = 0; i < vList.length; i++) {
            var e = vList[i];
            // 未被探测过的 才添加
            if (colors[e] == 'white') {
                colors[e] = 'gray';
                queue.enqueue(e);
            }
        };

        // 4.5 v已经被探测，并且访问顶点
        handler(v);

        // 4.6 将顶点设置为黑色
        colors[v] = 'black';
    }
    console.log(colors);
}

效果:

3.2 深度优先遍历:

总结:以上就是树的一些基本操作,了解更多,自行百度哈能力有限,目前只会这么多:baby:!