使用 BFS 寻找最短路径

怎么做

class Dictionary{
  constructor(){
    this.items = {}
  }
  // 查:
  has(key){
    // return !!this.items[key]
    return key in this.items
  }
  // 查:
  size(){
    return Object.values(this.items).length
  }
  get(key){
    if(this.has(key)){
       return this.items[key]
    }
    return undefined
  }
  keys(){
    return Object.keys(this.items)
  }
  values(){
    return Object.values(this.items)
  }
  // 增
  set(key,value){
    this.items[key] = value
  }
  // 删
  remove(key){
    if(this.has(key)){
          delete this.items[key]
          return true
    }
    return false
  }
}

class Queue {
    constructor(){
        this.items = []
    }
    // 增：队列增加一个元素
    enqueue(value){
        this.items.push(value)
    }
    // 删：出队列
    dequeue(){
        return this.items.shift()
    }
    // 删：清空队列
    clear(){
        return this.items = []
    }
    // 查：返回队列是否是空
    isEmpty(){
        return this.items.length === 0
    }
    // 查：返回队列的大小
    size(){
        return this.items.length
    }
}

class Stack{
    constructor(){
        this.items = []
    }
    // 增:栈顶增加一个元素
    push(value){
        this.items.push(value)
    }
    // 删：出栈
    pop(){
       return this.items.pop()
    }
    // 删：清空
    clear(){
        return this.items = []
    }
    // 查：返回栈是否是空
    isEmpty(){
        return this.items.length === 0
    }
    // 查：返回栈的大小
    size(){
        return this.items.length
    }
    // 查：返回栈顶元素
    peek(){
        return this.items[this.items.length-1]
    }
}

class Graph {
  constructor() {
    // 顶点列表
    this.vertices = []
    // 字典，用来存储邻接表
    this.adjList = new Dictionary()
  }

  // 增:添加顶点
  addVertex(vertex) {
    // 接受顶点作为参数，将该顶点添加到顶点列表中
    this.vertices.push(vertex)
    // 在邻接表中设置该顶点作为键对应的字典值为一个空数组
    this.adjList.set(vertex, [])
  }
  // 增:添加边（连接 vertex 中的顶点）
  addEdge(v1, v2) {
    // 首先，通过将v2加入到v1的邻接表中，我们添加了一条自顶点v1到顶点v2的边。
    this.adjList.get(v1).push(v2)
    // 由于我们做的是无向图，所以还需要添加一条自w向v的边
    this.adjList.get(v2).push(v1)
  }
  // 查:获取每个顶点的相邻点
  toString() {
    let str = ''
    for (let i = 0; i < this.vertices.length; i++) {
      str += `${this.vertices[i]} =>`
      // 然后，取该顶点的邻接表，并进行迭代，同样将迭代结果加入字符串中，
      let neighbors = this.adjList.get(this.vertices[i])
      for (let j = 0; j < neighbors.length; j++) {
        str += `${neighbors[j]} `
      }
      // 迭代完成后末尾加换行符，用于将每个顶点和它的邻接表在一行显示，最终得到一个漂亮的邻接表类型的图
      str += '\n'
    }
    return str
  }

  // 将图的所有顶点全部初始化为白色
  colors = {
    white: 0,
    gray: 1,
    black: 2
  }
  initializeColor() {
    const color = {}
    for (let i = 0; i < this.vertices.length; i++) {
      color[this.vertices[i]] = this.colors.white
    }
    return color
  }

  // 广度优先搜索(队列)
  bfs(v) {
    // 拿到初始化标记过状态之后的顶点的集合，是一个对象数组，将顶点作为key，颜色作为value
    let color = this.initializeColor()

    let queue = new Queue()
    // 创建 d对象，用来存储从顶点v到顶点u的距离d[u]
    let d = {}
    // 创建pred对象，用来存储搜索过程中 顶点v的前一个顶点。即：前溯点pred[u]，用来推导出从v到其他每个顶点u的最短路径
    let pred = {}

    queue.enqueue(v)

    // 同样的，我们遍历图的所有顶点的列表，将每个顶点都其他顶点的距离初始化为0
    for (let i = 0; i < this.vertices.length; i++) {
      // 记录每个顶点到其他顶点的距离
      d[this.vertices[i]] = 0
      pred[this.vertices[i]] = null
    }

    // 循环队列
    while (!queue.isEmpty()) {
      // 如果队列非空的话，继续执行以下的操作
      // 移除队列的第一项 u
      let u = queue.dequeue()
      // adjList字典中存储的是顶点和它的邻接顶点列表，所以我们拿到顶点u的邻接列表
      let neighbors = this.adjList.get(u)

      // 将访问过的顶点u的状态变更为灰色
      color[u] = 'gray'

      // 接着探索 顶点u的邻接列表
      for (let i = 0; i < neighbors.length; i++) {
        // 取出每个邻接顶点
        let w = neighbors[i]

        if (color[w] === this.colors['white']) {
          color[w] = this.colors['gray']

          d[w] = d[u] + 1
          pred[w] = u

          queue.enqueue(w)
        }
      }
      // 当我们将顶点u的所以邻接顶点完全访问完之后，将顶点u的状态变为黑色
      color[u] = 'black'
    }

    return {
      distances: d, // 起始顶点为A 到其他顶点的距离的集合
      predecessors: pred // 起始顶点为A 每个顶点的前溯顶点的集合（父级）
    }
  }
}

// 首先我们实例化一个图
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顶点
const shortestPathA = graph.bfs(myVertices[0]);
console.log(shortestPathA);

let fromVertex = myVertices[0]; // 即顶点A
// 遍历图的顶点列表
for (let i = 1; i < myVertices.length; i++) {
    // 记录下一个顶点
    let toVertex = myVertices[i];
    // 声明path 栈 用来记录路径
    let path = new Stack();
    // 追溯 toVertex 到 fromVertex的路径；变量v赋值为其前溯顶点的值，从而进行反向追溯路径
    for (let v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) {
        // 将顶点v 推入栈中
        path.push(v)
    }
    // 最终将源顶点也推入栈中，得到完整的路径
    path.push(fromVertex);
    // 栈的规则：先进后出，后进先出，所有我们创建变量s，将栈末尾的源顶点赋值给它。
    let s = path.pop();
    // 循环将栈中的顶点取出，拼接到s后面
    while(!path.isEmpty()) {
        s += ` - ${path.pop()}`
    }
    console.log(s)
}