/**
 * dict字典
 */

 function Dictionay() {
    this.items = {}

    // 在字典中添加键值对
    Dictionay.prototype.set = function (key, value) {
        this.items[key] = value
    }
    // 判断字典是否存在key
    Dictionay.prototype.has = function (key) {
        return this.items.hasOwnProperty(key)
    }
    // 从字典中移除元素
    Dictionay.prototype.remove = function (key) {
        if (!this.has(key)) return false
        delete this.items[key]
        return true
    }
    // 根据key获取value
    Dictionay.prototype.get = function (key) {
        return this.has(key) ? this.items[key] : undefined
    }
    // 获取所有的keys
    Dictionay.prototype.keys = function () {
        return Object.keys(this.items)
    }
}
/**
 * 队列
 */

// 1. 封装队列类(基于数组形式)
function Queue() {
    this.items = []

    Queue.prototype.enqueue = function (element) {
        this.items.push(element)
    }
    Queue.prototype.dequeue = 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 () {
        var itemsToString = ''
        this.items.forEach(item => {
            itemsToString += item + ','
        });
        return itemsToString
    }
}

/**
 * 图结构以及算法
 */

// 封装
function Graph() {
    // 属性
    this.vertexes = [] // 存储顶点
    this.adjList = new Dictionay() // 存储边
    
    // 添加顶点的方法
    Graph.prototype.addVertex = function (v) {
        this.vertexes.push(v)
        this.adjList.set(v, [])
    }
    // 添加边
    Graph.prototype.addEdge = function (v, w) {
        this.adjList.get(v).push(w)
        this.adjList.get(w).push(v)
    }
    // 转换为字符串
    Graph.prototype.toString = function () {
        var resultStr = ""
        for (var i = 0; i < this.vertexes.length; i++) {
            resultStr += this.vertexes[i] + "->"
            var adj = this.adjList.get(this.vertexes[i])
            for (var j = 0; j < adj.length; j++) {
                resultStr += adj[j] + " "
            }
            resultStr += "\n"
        }
        return resultStr
    }
    // 初始化颜色：广度优先算法
    Graph.prototype.initializeColor = function () {
        var colors = []
        for (var i = 0; i < this.vertexes.length; i++) {
            colors[this.vertexes[i]] = "white"
        }
        return colors
    }
    // 广度优先搜索
    Graph.prototype.bfs = function (v, handler) {
        // 1.初始化颜色
        var color = this.initializeColor()
    
        // 2.创建队列
        var queue = new Queue()
    
        // 3.将传入的顶点放入队列中
        queue.enqueue(v)
    
        // 4.从队列中依次取出和放入数据
        while (!queue.isEmpty()) {
            // 4.1.从队列中取出数据
            var qv = queue.dequeue()
    
            // 4.2.获取qv相邻的所有顶点
            var qAdj = this.adjList.get(qv)
    
            // 4.3.将qv的颜色设置成灰色
            color[qv] = "gray"
    
            // 4.4.将qAdj的所有顶点依次压入队列中
            for (var i = 0; i < qAdj.length; i++) {
                var a = qAdj[i]
                if (color[a] === "white") {
                    color[a] = "gray"
                    queue.enqueue(a)
                }
            }
    
            // 4.5.因为qv已经探测完毕, 将qv设置成黑色
            color[qv] = "black"
    
            // 4.6.处理qv
            if (handler) {
                handler(qv)
            }
        }
    }
    // 深度优先搜索算法
    // 深度优先搜索
    Graph.prototype.dfs = function (handler) {
        // 1.初始化颜色
        var color = this.initializeColor()

        // 2.遍历所有的顶点, 开始访问
        for (var i = 0; i < this.vertexes.length; i++) {
            if (color[this.vertexes[i]] === "white") {
                this.dfsVisit(this.vertexes[i], color, handler)
            }
        }
    }

    // dfs的递归调用方法
    Graph.prototype.dfsVisit = function (u, color, handler) {
        // 1.将u的颜色设置为灰色
        color[u] = "gray"
        // 2.处理u顶点
        if (handler) {
            handler(u)
        }
        // 3.u的所有邻接顶点的访问
        var uAdj = this.adjList.get(u)
        for (var i = 0; i < uAdj.length; i++) {
            var w = uAdj[i]
            if (color[w] === "white") {
                this.dfsVisit(w, color, handler)
            }
        }
        // 4.将u设置为黑色
        color[u] = "black"
    }
}

// 测试代码
var graph = new Graph()
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
for (var i = 0; i < myVertexes.length; i++) {
    graph.addVertex(myVertexes[i])
}

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())
/**
 * 输出结果:
        A->B C D 
        B->A E F 
        C->A D G 
        D->A C G H 
        E->B I 
        F->B 
        G->C D 
        H->D 
        I->E
 */

// 调用广度优先算法
var result = ""
graph.bfs(graph.vertexes[0], function (v) {
    result += v + " "
})
console.log(result) // A B C D E F G H I