图:广度优先遍历(BFS)和深度优先遍历(DFS)

1.工具类：队列和字典

export class DictionNary {
    // 字典的封装
    constructor() {
        this.items = {}
    }
    set(key, value) {
        // 添加键
        this.items[key] = value
    }
    has(key){
        // 判断键是否存在
        return this.items.hasOwnProperty(key)
    }
    get(key){
        // 获取键的value
        return this.has(key) ? this.items[key] : undefined
    }
    remove (key){
        // 删除键
        if(this.has(key)){
            delete this.items[key]
            return true
        }
        return false
    }
    keys(){
        // 获取所有的键
        return Object.keys(this.items)
    }
    values(){
        // 获取所有的值
        return Object
    }
    size(){
        // 获取键值对的数量
        return this.keys().length
    }
    clear(){
        // 清空字典
        this.items = {}
    }
    toString(){
        // 转换为字符串
        if(this.size() > 0){
            let objString = `{${this.keys().join(',')}}`
            return objString
        }else{
            return '{}'
        }
    }
}

export class Queue {
    // 队列的封装
    constructor() {
        this.items = []
    }
    // 方法
    enqueue(element) {
        // 添加元素到队列
        this.items.push(element)
    }
    dequeue() {
        // 移除队列的第一个元素
        return this.items.shift()
    }
    front() {
        // 返回队列的第一个元素
        return this.items[0]
    }
    isEmpty() {
        // 判断队列是否为空
        return this.items.length == 0
    }
    size() {
        // 返回队列的元素个数
        return this.items.length
    }
    toString() {
        return this.items.toString()
    }
    
}

2. 图的封装

class Graph {
        constructor() {
            // 顶点
            this.vertexes = []
            // 边
            this.edges = new DictionNary()
        }
        // 方法
        addVertex(v){
            // 添加顶点
            this.vertexes.push(v)
            // 顶点对于边数组的初始化
            this.edges.set(v, [])
        }
        addEdge(v1, v2){
            // 无向图中边的设置
            this.edges.get(v1).push(v2)
            this.edges.get(v2).push(v1)
        }
        toString(){
            let result = ''
            for(let i = 0; i < this.vertexes.length; i++){
                result += this.vertexes[i] + ' -> '
                const neighbors = this.edges.get(this.vertexes[i])
                for(let j = 0; j < neighbors.length; j++){
                    result += neighbors[j] + ' '
                }
                result += '\n'
            }
            return result
        }
        initializeColor(){
            // 顶点遍历颜色初始化
            const colors = []
            for(let i = 0; i < this.vertexes.length; i++){
                colors[this.vertexes[i]] = 'white'
            }
            return colors
        }
        
        bfs(firstVertex, callback){
            // 广度优先遍历
            // 顶点遍历测试
            // 1.层序遍历：Breadth-First Search (BFS)
            // 2.深度遍历：Depth-First Search (DFS)
            // 3.为了记录顶点是否被访问过，我们使用三种颜色定义顶点的状态
                // 1.白色：表示该顶点还没有被访问
                // 2.灰色：表示该顶点被访问过，但并未被探索(被探索意思是其所有相邻顶点都被访问过)
                // 3.黑色：表示该顶点被访问过且被完全探索
            // 1.初始化顶点颜色
           const colors = this.initializeColor()
           // 2.创建队列
           const queue = new Queue()
           // 3.将第一个顶点加入队列
           queue.enqueue(firstVertex)
           // 4.循环遍历队列
           while(!queue.isEmpty()){
            // 4.1.从队列中取出一个顶点
               const v = queue.dequeue()
               // 4.2.获取和该顶点相邻的顶点
               const neighbors = this.edges.get(v)
               // 4.3.将当前顶点的颜色设置为灰色（被访问过）   
               colors[v] = 'gray'
               // 4.4.遍历该顶点的所有相邻顶点
               for(let i = 0; i < neighbors.length; i++){
                   const w = neighbors[i]
                   if(colors[w] === 'white'){
                       colors[w] = 'gray'
                       queue.enqueue(w) 
                   }
               }
               // 4.5.将当前顶点设置为黑色（被探索）
               colors[v] = 'black'
               // 4.6.调用callback函数
               callback(v)
           }
        }

        dfs(initVertex, callback){
            // 1.初始化颜色
            const colors = this.initializeColor()
            // 2.递归函数
            this.dfsVisit(initVertex, colors, callback)
            
        }
        dfsVisit(vertexes, colors, callback){
            // 1.访问过节点置灰色
            colors[vertexes] = 'gray'
            // 2.调用callback函数
            callback(vertexes)
            // 3.获取和该顶点相邻的顶点
            const neighbors = this.edges.get(vertexes)
            for(let i = 0; i < neighbors.length; i++){
                const w = neighbors[i]
                if(colors[w] === 'white'){
                    this.dfsVisit(w, colors, callback)
                }
            }
            // 4.访问完节点置黑色
            colors[vertexes] = 'black'
        }

    }

图测试用例

 const graph = new Graph()
    // 1.添加顶点
    const myVertices = ['A', 'B', 'C', 'D', 'E', 'F','G', 'H','I']
    for(let i = 0; i < myVertices.length; i++){
        graph.addVertex(myVertices[i])
    }
    // 2.添加边
    graph.addEdge('A', 'B')
    graph.addEdge('A', 'C')
    graph.addEdge('A', 'D')
    graph.addEdge('C', 'D')
    graph.addEdge('C', 'G')
    graph.addEdge('D', 'G')
    graph.addEdge('D', 'H')
    graph.addEdge('B', 'E')
    graph.addEdge('B', 'F')
    graph.addEdge('E', 'I')

    console.log(graph.toString())
    
    // 测试广度优先遍历
    let result = ''
    graph.bfs(graph.vertexes[0], function(v){
        result += v + ' '
    })
    console.log(result)

    // 测试深度优先遍历
    let deepRsult = ''
    graph.dfs(graph.vertexes[0], function(v){
        deepRsult += v + ' '
    })
    console.log(deepRsult)