JS实现广度优先搜索与深度优先搜索

图在数学及技术上的概念：
一个图G = (V, E)，由以下元素组成。
 V: 一组顶点
 E: 一组边，连接V中的顶点

  在着手实现算法之前，让我们先了解一下图的一些术语。

  由一条边连接在一起的顶点称为相邻顶点。比如，A和B是相邻的，A和D是相邻的，A和C是相邻的，A和E不是相邻的。

   一个顶点的度是其相邻顶点的数量。比如，A和其他三个顶点相连接，因此，A的度为3; E和其他两个顶点相连，因此，E的度为2。

  路径是顶点v1, v2, ..., vk的一个连续序列，其中vi和vi+1是相邻的。以上一示意图中的图为例，其中包含路径A B E I和A C D G。

  简单路径要求不包含重复的顶点。举个例子，A D G是一条简单路径。除去最后一个顶点(因为它和第一个顶点是同一个顶点)，环也是一个简单路径，比如A D C A(最后一个顶点重新回到A)。

  如果图中不存在环，则称该图是无环的。如果图中每两个顶点间都存在路径，则该图是联通的。

  我们可以使用图来解决计算机科学世界中的很多问题，比如搜索图中的一个特定顶点或搜索一条特定边，寻找图中的一条路径(从一个顶点到另一个顶点)，寻找两个顶点之间的最短路径， 以及环检测。

图的表示

邻接矩阵

邻接表

关联矩阵

  我们用JS来实现图：

function Dictionary() {
    let items = {}
    this.set = function (key, value) {
        items[key] = value
    }
    this.has = function (key) {
        return key in items
    }
    this.remove = function (key) {
        if (this.has(key)) {
            delete items[key]
            return true
        }
        return false
    }
    this.get = function (key) {
        return this.has(key) ? items[key] : undefined
    }
    this.values = function () {
        let values = []
        for (let k in items) {
            if (this.has(k)) {
                values.push(items[k])
            }
        }
        return values
    }
    this.clear = function () {
        items = []
    }
    this.size = function () {
        return Object.keys(items).length
    }
    this.keys = function () {
        return Object.keys(items)
    }
    this.getItems = function () {
        return items
    }
}

function Graph() {

    let vertices = [] // 存储图中所有顶点的名字
    let adjList = new Dictionary() // 字典储存邻接表，使用顶点的名字作为键，邻接顶点列表作为值

    // 向图中添加一个新的顶点
    this.addVertex = function (v) {
        vertices.push(v)
        adjList.set(v, [])
    }

    // 添加顶点之间的边
    this.addEdge = function (v, w) {
        adjList.get(v).push(w)
        adjList.get(w).push(v)
    }

    this.toString = function() {
        let s = ''
        for (let i = 0; i < vertices.length; i++){
            s += vertices[i] + ' -> '
            let neighbors = adjList.get(vertices[i])
            for (let j = 0; j < neighbors.length; j++){
                s += neighbors[j] + ' '
            }
            s += '\n'
        }
        return s;
    };
}

let graph = new Graph()
let myVertices = ['A','B','C','D','E','F','G','H','I']
for (let i = 0; i < myVertices.length; i++){
    graph.addVertex(myVertices[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 

图的遍历
  和树数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历：广度优先搜索(Breadth-First Search，BFS)和深度优先搜索(Depth-First Search，DFS)。
  图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环等。
  图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。
  完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。
  为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。
  广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点列表的数据结构。

广度优先搜索
  广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深地访问顶点，如下图所示:

当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态。
 白色: 表示该顶点还没有被访问。
 灰色: 表示该顶点被访问过，但并未被探索过。
 黑色: 表示该顶点被访问过且被完全探索过。
这就是之前提到的务必访问每个顶点最多两次的原因。

function Queue() {
    let items = []
    this.enqueue = function (element) {
        items.push(element)
    }
    this.dequeue = function () {
        return items.shift()
    }
    this.front = function () {
        return items[0]
    }
    this.isEmpty = function () {
        return items.length == 0
    }
    this.clear = function () {
        items = []
    }
    this.size = function () {
        return items.length
    }
    this.print = function () {
        console.log(items.toString())
    }
}

function Dictionary() {
    let items = {}
    this.set = function (key, value) {
        items[key] = value
    }
    this.has = function (key) {
        return key in items
    }
    this.remove = function (key) {
        if (this.has(key)) {
            delete items[key]
            return true
        }
        return false
    }
    this.get = function (key) {
        return this.has(key) ? items[key] : undefined
    }
    this.values = function () {
        let values = []
        for (let k in items) {
            if (this.has(k)) {
                values.push(items[k])
            }
        }
        return values
    }
    this.clear = function () {
        items = []
    }
    this.size = function () {
        return Object.keys(items).length
    }
    this.keys = function () {
        return Object.keys(items)
    }
    this.getItems = function () {
        return items
    }
}

function Graph() {

    let vertices = [] // 存储图中所有顶点的名字
    let adjList = new Dictionary() // 字典储存邻接表，使用顶点的名字作为键，邻接顶点列表作为值

    // 向图中添加一个新的顶点
    this.addVertex = function (v) {
        vertices.push(v)
        adjList.set(v, [])
    }

    // 添加顶点之间的边
    this.addEdge = function (v, w) {
        adjList.get(v).push(w)
        adjList.get(w).push(v)
    }

    // 在控制台输出图
    this.toString = function(){
        let s = ''
        for (let i = 0; i < vertices.length; i++){
            s += vertices[i] + ' -> '
            let neighbors = adjList.get(vertices[i])
            for (let j = 0; j < neighbors.length; j++){
                s += neighbors[j] + ' '
            }
            s += '\n'
        }
        return s;
    }

    // 广度优先搜索算法
    let initializeColor = function () {
        let color = []
        for (let i = 0; i < vertices.length; i++) {
            color[vertices[i]] = 'white' // 顶点还没有被访问过
        }
        return color
    }
    this.bfs = function (v, callback) {
        let color = initializeColor(),
            queue = new Queue()
        queue.enqueue(v)
        while (!queue.isEmpty()) {
            let u = queue.dequeue(),
                neighbors = adjList.get(u)
            color[u] = 'grey'
            for (let i = 0; i < neighbors.length; i++) {
                let w = neighbors[i]
                if (color[w] === 'white') {
                    color[w] = 'grey'
                    queue.enqueue(w)
                }
            }
            color[u] = 'black'
            if (callback) {
                callback(u)
            }
        }
    }

}
function printNode (value) {
    console.log('Visited vertex: ' + value)
}


let graph = new Graph()
let myVertices = ['A','B','C','D','E','F','G','H','I']
for (let i = 0; i < myVertices.length; i++){
    graph.addVertex(myVertices[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')

graph.bfs(myVertices[0], printNode)
// Visited vertex: A
// Visited vertex: B
// Visited vertex: C
// Visited vertex: D
// Visited vertex: E
// Visited vertex: F
// Visited vertex: G
// Visited vertex: H
// Visited vertex: I

使用BFS寻找最短路径
  给定一个图G和源顶点v，找出对每个顶点u，u和v之间最短路径的距离(以边的数量计)。
  对于给定顶点v，广度优先算法会访问所有与其距离为1的顶点，接着是距离为2的顶点， 以此类推。所以，可以用广度优先算法来解这个问题。
 从v到u的距离d[u];
 前溯点pred[u]，用来推导出从v到其他每个顶点u的最短路径。

// 改进过的广度优先搜索算法
    this.BFS = function (v) {
        let color = initializeColor(),
            queue = new Queue(),
            d = [], // v到u的距离
            pred = [] // 前溯点p
        queue.enqueue(v)

        for (let i = 0; i < vertices.length; i++) {
            d[vertices[i]] = 0
            pred[vertices[i]] = null
        }

        while (!queue.isEmpty()) {
            let u = queue.dequeue(),
                neighbors = adjList.get(u)
            color[u] = 'grey'
            for (let i = 0; i < neighbors.length; i++) {
                let w = neighbors[i]
                if (color[w] === 'white') {
                    color[w] = 'grey'
                    d[w] = d[u] + 1
                    pred[w] = u
                    queue.enqueue(w)
                }
            }
            color[u] = 'black'
        }

        return {
            distances: d,
            predecessors: pred
        }
    }

  通过前溯点数组，我们可以用下面这段代码来构建从顶点A到其他顶点的路径:

// 对predecessors进行追溯直到A点，然后展示回溯路径
let fromVertex = myVertices[0]
for (let i = 1; i < myVertices.length; i++){
    let toVertex = myVertices[i],
        path = new Stack()
    for (let v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
        path.push(v)
    }
    path.push(fromVertex)
    let s = path.pop()
    while (!path.isEmpty()) {
        s += ' - ' + path.pop()
    }
    console.log(s)
}
// A - B
// A - C
// A - D
// A - B - E
// A - B - F
// A - C - G
// A - D - H
// A - B - E - I

深度优先搜索
  深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点被访问了，接着原路回退并探索下一条路径。

  深度优先搜索算法不需要一个源顶点。在深度优先搜索算法中，若图中顶点v未访问，则访问该顶点v。

要访问顶点v，照如下步骤做。
(1) 标注v为被发现的(灰色)。
(2) 对于v的所有未访问的邻点w，访问顶点w，标注v为已被探索的(黑色)。

 // 深度优先算法
    let dfsVisit = function(u, color, callback){
        color[u] = 'grey'
        if (callback) {
            callback(u)
        }
        let neighbors = adjList.get(u);
        for (let i = 0; i < neighbors.length; i++){
            let w = neighbors[i]
            if (color[w] === 'white'){
                dfsVisit(w, color, callback)
            }
        }
        color[u] = 'black'
    }
    this.dfs = function(callback){
        let color = initializeColor()
        for (let i = 0; i < vertices.length; i++){
            if (color[vertices[i]] === 'white'){
                dfsVisit(vertices[i], color, callback)
            }
        }
    }

console.log(graph.dfs(printNode))
// Visited vertex: A
// Visited vertex: B
// Visited vertex: E
// Visited vertex: I
// Visited vertex: F
// Visited vertex: C
// Visited vertex: D
// Visited vertex: G
// Visited vertex: H

完整代码：

function Stack() {
    let items = []
    this.push = function (element) {  // 添加一个（或几个）新元素到栈顶
        items.push(element)
    }
    this.pop = function (element) { // 移除栈顶的元素，同时返回被移除的元素
        return items.pop()
    }
    this.peek = function (element) { // 返回栈顶的元素，不对栈做任何修改
        return items[items.length - 1]
    }
    this.isEmpty = function (element) {// 如果栈里没有任何元素就返回true
        return items.length === 0
    }
    this.size = function () { // 返回栈里的元素个数
        return items.length
    }
    this.clear = function () { // 移除栈里的所有元素
        items = []
    }
    this.print = function () { // 字符串化
        console.log(items.toString())
    }
}

function Queue() {
    let items = []
    this.enqueue = function (element) {
        items.push(element)
    }
    this.dequeue = function () {
        return items.shift()
    }
    this.front = function () {
        return items[0]
    }
    this.isEmpty = function () {
        return items.length == 0
    }
    this.clear = function () {
        items = []
    }
    this.size = function () {
        return items.length
    }
    this.print = function () {
        console.log(items.toString())
    }
}

function Dictionary() {
    let items = {}
    this.set = function (key, value) {
        items[key] = value
    }
    this.has = function (key) {
        return key in items
    }
    this.remove = function (key) {
        if (this.has(key)) {
            delete items[key]
            return true
        }
        return false
    }
    this.get = function (key) {
        return this.has(key) ? items[key] : undefined
    }
    this.values = function () {
        let values = []
        for (let k in items) {
            if (this.has(k)) {
                values.push(items[k])
            }
        }
        return values
    }
    this.clear = function () {
        items = []
    }
    this.size = function () {
        return Object.keys(items).length
    }
    this.keys = function () {
        return Object.keys(items)
    }
    this.getItems = function () {
        return items
    }
}

function Graph() {

    let vertices = [] // 存储图中所有顶点的名字
    let adjList = new Dictionary() // 字典储存邻接表，使用顶点的名字作为键，邻接顶点列表作为值

    // 向图中添加一个新的顶点
    this.addVertex = function (v) {
        vertices.push(v)
        adjList.set(v, [])
    }

    // 添加顶点之间的边
    this.addEdge = function (v, w) {
        adjList.get(v).push(w)
        adjList.get(w).push(v)
    }

    // 在控制台输出图
    this.toString = function(){
        let s = ''
        for (let i = 0; i < vertices.length; i++){
            s += vertices[i] + ' -> '
            let neighbors = adjList.get(vertices[i])
            for (let j = 0; j < neighbors.length; j++){
                s += neighbors[j] + ' '
            }
            s += '\n'
        }
        return s;
    }

    // 广度优先搜索算法
    let initializeColor = function () {
        let color = []
        for (let i = 0; i < vertices.length; i++) {
            color[vertices[i]] = 'white' // 顶点还没有被访问过
        }
        return color
    }
    this.bfs = function (v, callback) {
        let color = initializeColor(),
            queue = new Queue()
        queue.enqueue(v)
        while (!queue.isEmpty()) {
            let u = queue.dequeue(),
                neighbors = adjList.get(u)
            color[u] = 'grey'
            for (let i = 0; i < neighbors.length; i++) {
                let w = neighbors[i]
                if (color[w] === 'white') {
                    color[w] = 'grey'
                    queue.enqueue(w)
                }
            }
            color[u] = 'black'
            if (callback) {
                callback(u)
            }
        }
    }

    // 改进过的广度优先搜索算法
    this.BFS = function (v) {
        let color = initializeColor(),
            queue = new Queue(),
            d = [], // v到u的距离
            pred = [] // 前溯点p
        queue.enqueue(v)

        for (let i = 0; i < vertices.length; i++) {
            d[vertices[i]] = 0
            pred[vertices[i]] = null
        }

        while (!queue.isEmpty()) {
            let u = queue.dequeue(),
                neighbors = adjList.get(u)
            color[u] = 'grey'
            for (let i = 0; i < neighbors.length; i++) {
                let w = neighbors[i]
                if (color[w] === 'white') {
                    color[w] = 'grey'
                    d[w] = d[u] + 1
                    pred[w] = u
                    queue.enqueue(w)
                }
            }
            color[u] = 'black'
        }

        return {
            distances: d,
            predecessors: pred
        }
    }

    // 深度优先算法
    let dfsVisit = function(u, color, callback){
        color[u] = 'grey'
        if (callback) {
            callback(u)
        }
        let neighbors = adjList.get(u);
        for (let i = 0; i < neighbors.length; i++){
            let w = neighbors[i]
            if (color[w] === 'white'){
                dfsVisit(w, color, callback)
            }
        }
        color[u] = 'black'
    }
    this.dfs = function(callback){
        let color = initializeColor()
        for (let i = 0; i < vertices.length; i++){
            if (color[vertices[i]] === 'white'){
                dfsVisit(vertices[i], color, callback)
            }
        }
    }

    // 探索深度优先算法
    let time = 0;
    this.DFS = function(){
        let color = initializeColor(),
            d = [], // 顶点u的发现时间
            f = [], // 当顶点u被标注为黑色时，u的完成探索时间
            p = [] // 顶点u的前溯点
        time = 0;
        for (let i = 0; i < vertices.length; i++){
            f[vertices[i]] = 0;
            d[vertices[i]] = 0;
            p[vertices[i]] = null;
        }
        for (let i = 0; i < vertices.length; i++){
            if (color[vertices[i]] === 'white'){
                DFSVisit(vertices[i], color, d, f, p);
            }
        }
        return {
            discovery: d,
            finished: f,
            predecessors: p
        }
    }
    let DFSVisit = function(u, color, d, f, p){
        console.log('discovered ' + u)
        color[u] = 'grey'
        d[u] = ++time
        let neighbors = adjList.get(u)
        for (let i = 0; i < neighbors.length; i++){
            let w = neighbors[i]
            if (color[w] === 'white'){
                p[w] = u
                DFSVisit(w,color, d, f, p)
            }
        }
        color[u] = 'black'
        f[u] = ++time
        console.log('explored ' + u)
    }
}

function printNode (value) {
    console.log('Visited vertex: ' + value)
}

let graph = new Graph()
let myVertices = ['A','B','C','D','E','F','G','H','I']
for (let i = 0; i < myVertices.length; i++){
    graph.addVertex(myVertices[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')

graph.bfs(myVertices[0], printNode)
// Visited vertex: A
// Visited vertex: B
// Visited vertex: C
// Visited vertex: D
// Visited vertex: E
// Visited vertex: F
// Visited vertex: G
// Visited vertex: H
// Visited vertex: I

console.log(graph.BFS(myVertices[0]))
// { distances: [ A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3 ],
//     predecessors:
//         [ A: null,
//     B: 'A',
//     C: 'A',
//     D: 'A',
//     E: 'B',
//     F: 'B',
//     G: 'C',
//     H: 'D',
//     I: 'E' ] }

// 对predecessors进行追溯直到A点，然后展示回溯路径
let shortestPathA = graph.BFS(myVertices[0])
let fromVertex = myVertices[0]
for (let i = 1; i < myVertices.length; i++){
    let toVertex = myVertices[i],
        path = new Stack()
    for (let v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
        path.push(v)
    }
    path.push(fromVertex)
    let s = path.pop()
    while (!path.isEmpty()) {
        s += ' - ' + path.pop()
    }
    console.log(s)
}
// A - B
// A - C
// A - D
// A - B - E
// A - B - F
// A - C - G
// A - D - H
// A - B - E - I


console.log(graph.dfs(printNode))
// Visited vertex: A
// Visited vertex: B
// Visited vertex: E
// Visited vertex: I
// Visited vertex: F
// Visited vertex: C
// Visited vertex: D
// Visited vertex: G
// Visited vertex: H

console.log(graph.DFS())
// discovered A
// discovered B
// discovered E
// discovered I
// explored I
// explored E
// discovered F
// explored F
// explored B
// discovered C
// discovered D
// discovered G
// explored G
// discovered H
// explored H
// explored D
// explored C
// explored A
// { discovery: [ A: 1, B: 2, C: 10, D: 11, E: 3, F: 7, G: 12, H: 14, I: 4 ],
//     finished:
//         [ A: 18, B: 9, C: 17, D: 16, E: 6, F: 8, G: 13, H: 15, I: 5 ],
//     predecessors:
//         [ A: null,
//     B: 'A',
//     C: 'A',
//     D: 'C',
//     E: 'B',
//     F: 'B',
//     G: 'D',
//     H: 'D',
//     I: 'E' ] }