javascript 实现无向图结构的封装并完成广度优先搜索和深度优先搜索

图的封装需要用到队列以及字典的封装结构
代码如下：

//封装队列类 队列的特点 从后端插入元素 从前端删除（取）元素
function Queue() {
    this.items = []

    //将元素加入到队列中
    Queue.prototype.enQueue = function (element) {
        this.items.push(element)
    }
    //前端删除队列元素
    Queue.prototype.delQueue = function () {
        return this.items.shift()
    }
    //查看前端的元素
    Queue.prototype.front = function () {
        return this.items[0]
    }
    //查看队列是否为空
    Queue.prototype.isEmpty = function () {
        return this.items.length === 0
    }
    //查看队列中元素的个数
    Queue.prototype.size = function () {
        return this.items.length
    }
    //将队列中的元素转化为字符串
    Queue.prototype.toString = function () {
        let resultString = ''
        for (let i = 0 ; i < this.items.length; i++) {
            resultString += this.items[i] + ' '
        }
        return resultString
    }
}

module.exports = Queue

//封装字典
function Dictionary() {
    this.items = {}

    //添加键值对
    Dictionary.prototype.set = function (key,value) {
        this.items[key] = value
    }

    判断是否存在某个key
    Dictionary.prototype.has = function (key) {
        return this.items.hasOwnProperty(key)
    }

    //移除字典中的元素
    Dictionary.prototype.remove = function (key) {
        if (!this.has(key)) return false

        delete this.items[key]
        return true
    }

    //获取value
    Dictionary.prototype.get = function (key) {
        return this.items[key] ? this.items[key] : undefined
    }

    //获取keys
    Dictionary.prototype.keys = function () {
        return Object.keys(this.items)
    }

    //获取values
    Dictionary.prototype.values = function () {
        return Object.values(this.items)
    }

    //size
    Dictionary.prototype.size = function () {
        return this.keys().length
    }

    //clear
    Dictionary.prototype.clear = function () {
        this.items = {}
    }
}

module.exports = Dictionary

封装的图结构的完整代码如下：

const dict = require('./dict')
const queue = require('./queue')
//封装图
function Graph() {

    this.vertexes = [] //顶点数组
    this.edges = new dict() //存储边

    //添加顶点
    Graph.prototype.addVertex = function (v) {
        this.vertexes.push(v)
        this.edges.set(v,[])
    }

    //添加边
    Graph.prototype.addEdge = function (v1,v2) {
        this.edges.get(v1).push(v2)
        this.edges.get(v2).push(v1)

    }

    //toString() 
    Graph.prototype.toString = function () {
        let resultString = ''
        for (let i = 0; i < this.vertexes.length; i++) {
            resultString += this.vertexes[i] + ' -> '
            let array = this.edges.get(this.vertexes[i])
            for (let j = 0; j < array.length; j++) {
                resultString += array[j] + ' '
            }
            resultString += '\n'
        }
       return resultString
    }

    //初始化顶点的状态颜色
    Graph.prototype.initializeColor = function () {
        let colors = []

        for (let i = 0; i < this.vertexes.length; i++) {
            colors[this.vertexes[i]] = 'white' //白色表示未被访问
        }
        return colors
    }

    //BFS 广度优先搜索
    Graph.prototype.bfs = function (initV,handler) {
        let colors = this.initializeColor()

        let queueList = new queue()

        queueList.enQueue(initV)
        colors[initV] = 'black' //访问过后变成黑色
        while(!queueList.isEmpty()) {
            let v = queueList.delQueue()

            let vList = this.edges.get(v)

            for (let i = 0; i < vList.length; i++) {
                if (colors[vList[i]] === 'white') {
                    queueList.enQueue(vList[i])
                    colors[vList[i]] = 'black'
                }
            }
            handler(v)

        }
    }

    //DFS 深度优先搜索
    Graph.prototype.dfs = function (initV,handler) {
        let colors = this.initializeColor()

        this.dfsVisit(initV,colors,handler)
    }

    //递归
    Graph.prototype.dfsVisit = function (v,colors,handler) {
        colors[v] = 'black'
        handler(v)
        let vList = this.edges.get(v)
        for (let i = 0; i < vList.length; i++) {
            if (colors[vList[i]] === 'white') {
                this.dfsVisit(vList[i],colors,handler)
            }
        }
    }

}

打印一下封装的图的内部结构：

const gg = new Graph()
let  myVertex = ['A','B','C','D','E','F','G','H','I']
for (let i = 0 ; i< myVertex.length ; i++) {
    gg.addVertex(myVertex[i])
}
gg.addEdge('A','B')
gg.addEdge('A','C')
gg.addEdge('A','D')
gg.addEdge('C','D')
gg.addEdge('C','G')
gg.addEdge('D','G')
gg.addEdge('D','H')
gg.addEdge('B','E')
gg.addEdge('B','F')
gg.addEdge('E','I')
console.log(gg)

//打印的结果

Graph {
  vertexes: [ //存放顶点的数组
    'A', 'B', 'C',
    'D', 'E', 'F',
    'G', 'H', 'I'
  ],
  edges: Dictionary { //存放边的数组
    items: { //每个顶点对应的数组存放的是与该顶点形成边的另一个顶点
      A: [Array], 
      B: [Array],
      C: [Array],
      D: [Array],
      E: [Array],
      F: [Array],
      G: [Array],
      H: [Array],
      I: [Array]
    }
  }
}
//bfs和dfs封装在图结构的内部