// 封装图结构   这里需要自己引入封装的字典/对象和队列
function Graph() {

    // 属性 1、顶点、 2边  边是一个字典/对象，字典/对象里面的建就是顶点，值[] 里面放和顶点有连线的顶点
    this.vertexes = []
    const edges = new derectory()


    // 1、添加顶点的方法  我在添加这个顶点的同时 我需要给他同时创建一个字典/对象来保存边的数据
    this.addVertex = function (v) {
        this.vertexes.push(v)
        this.edges.set(v, [])
    }

    // 2、添加边的方法  v1是要往哪个顶点添加边，v2是你要添加的顶点  两个顶点会连成一条线
    this.addEdge = function (v1, v2) {
        // if (v1 === v2) return false 是否需要判断
        // 无向图应该是互相连线的
        this.edges.get(v1).push(v2)
        this.edges.get(v2).push(v1)
    }

    // 3、返回边的邻近表字符串
    this.toString = function () {
        let resStr = ''
        for (let i of vertexes) {
            resStr += i + '->'
            let edgesArr = this.edges.get(i) //这里返回的是一个数组
            for (let j of edgesArr) {
                resStr += j + ' ' //继续往后拼接 每一个字符串都往后连续拼接 j 直到循环完毕 再返回第一个循环的起点
            }
            resStr += '\n'
        }
    }
    // 4.1、初始化状态颜色
    this.initColor = function () {
        let color = []
        for (let i in this.vertexes) {
            colors[this.vertexes[i]] = 'white' //数组本身也是一种对象 数组的下标也能改变
        }
        return color
    }
    let bstArr = []
    // 4.2、广度优先遍历 广度优先采用队列作为基础数据结构 
    // 1、传入起始顶点作为参数,firstV 无论是广度优先还是深度优先都需要一个起始点
    this.bst = function (firstV) {
        // 2、要用到队列，所以构造一个实例对象
        const queue = new Queue()
        // 3、用状态颜色来判断顶点是否被访问过
        let color = this.initColor()
        // 先将起始点进队
        queue.enQueue(firstV)
        // 只要队列里还有顶点就循环
        while (!this.queue.size) {
            // 第一个顶点先出队，并且颜色改为已访问过的grey
            let outV = queue.deQueue() //第二次outV已经变成了下一个顶点
            color[outV] = 'grey'
            // 此时遍历他的边
            for (let i of this.edges.get(outV)) {
                queue.enQueue(i)
                if (color[i] === 'white') {
                    color[i] = 'grey'
                }
            }
            // push的应该是每次从队列出去的顶点 第一次outV为你传入的起点，第二次变为他的边顶点
            this.bstArr.push(outV)
            color(outV) = 'black'
        }
    }
    let dftArr = []
    // 5.1、深度优先遍历 deep-first traversal
    this.dft = function (firstV) {
        // 不能把初始化颜色写在递归函数里，这样递归过程中会把他再初始化
        let color = this.initColor
        return this.dftRecursion(firstV, color)
    }
    //5.2、深度优先遍历的递归函数
    this.dftRecursion = function (firstV, color) {

        // 1、从firstV开始 被访问过的顶点变为灰色
        color[firstV] = 'grey'

        // 2、按遍历顺序处理顶点
        this.dftArr[firstV]

        // 3、这时候要访问他的边顶点了
        for (let i of this.edges.get[firstV]) {
            // 此时i为B 此时就应该调用递归函数 遍历B的边顶点
            if (color[i] === 'white')
                this.dftRecursion(i, color)
        }

        // 4、遍历过渡顶点为黑色
        color[firstV] = 'black'
    }
}

总结
1、图结构需要的属性为顶点和边，边用字典表示最好，key为顶点，value为与顶点有连线的其他顶点数组
2、添加顶点时需要同时为这个顶点创建一个对应的空字典，保存之后的连线顶点
3、有向图是只能A到B或者B到A ，无向图是可以互相通行，所以无向图的连线应该是互相的
4、图结构的广度优先遍历 (采用队列) 和深度优先遍历 (采用递归) 都需要一个初始顶点，并且应该用颜色状态来表示是否被访问过和处理过

广度优先搜索.png

深度优先搜索.png