数据结构(八)-图，深度优先(图的遍历)，广度优先(图的遍历)

图是网络结构抽象模型

图的相关术语

1
2
3

一个图G = (V,E)
V:一组顶点
E:一组边

相邻顶点:比如上图A,B，A,C,A,D都是相邻顶点，A,E不是
顶点的度:相邻顶点的数量。A和B,C,D相邻，那么A的度就是3，E和其他两个顶点相邻，E的度为2
路径:路径是顶点的一个连续序列，比如A,B,E,I,A,C,D,G
有向图，无向图:无向图(边没有方向)，有向图(边有方向)，下面的边有一个方向，是有向图，C,D互相双向存在路径，称之为强连通，A,C不是强连通
加权:下图就是边被赋予了权值

图可以用来解决寻找最短路径，环检测等。

图的三种不同表示

邻接矩阵

掘金上有一篇通过邻接矩阵实现表单联动的算法链接

下面这张图是数据化以后的邻接矩阵

如果为相邻节点，则节点值为1，否则节点值为0。

比如节点A，B相邻，那么坐标(A,B)和坐标(B,A)这两个点的值就是1

邻接表

除了上面的邻接矩阵可以表示图，还可以使用邻接表，可以使用列表数组，链表，散列表或者是字典来表示相邻顶点列表

图的遍历

有两种算法可以对图进行遍历:广度优先搜索(BFS),**深度优先搜索(DFS)**。

图遍历可以用来寻找特定的顶点或者寻找两个顶点之间的路径，检查图是否连通，检查是否有环。

三种颜色表示当前顶点状态

白色:没有被访问
灰色:表示被发现但是并没探索
黑色:表示顶点被访问并且完全探索过

基础骨架代码

const Colors = {
    WHITE:0,
    GERY:1,
    BLACK:2
}

const initializeColor = vertices => {
    const color = {}
    for (let i = 0; i < vertices.length; i++) {
        color[vertices[i]] = Colors.WHITE
    }
    return color
}

广度优先搜索

图示算法过程:https://www.cnblogs.com/huansky/p/12826857.html
使用队列数据结构，会从第一个顶点开始遍历图，先访问所有邻点，先宽后深，由上到下一级一级访问。

访问路径为A,B,C,D,E,F,G,H,I
算法过程如下:

创建一个队列Q
标注顶点v为被发现(灰色)
如果队列Q不为空，则:
- 将队列Q中的u取出
- 标注u为被发现(灰色)
- 将u所有未被访问过的邻点(白色)入队列

标注u为已被探索(黑色)
可以参考这篇文章，讲得比较清楚,https://www.cnblogs.com/huansky/p/12826857.html

//#region 字典，实现邻接表
  class Dictionary {
    constructor(toStrFn = defaultToString) {
      this.toStrFn = toStrFn
      this.table = {}
    }
    hasKey (key) {
      return !!this.table[this.toStrFn(key)]
    }
    removeKey (key) {
      if (this.hasKey[key]) {
        delete this.table[this.toStrFn(key)]
        return true
      }
      return false
    }
    set(key,value) {
      if (key !== null && value !== null) {
        // value是一个ValuePair类，同时保存了当前的key以及value
        this.table[this.toStrFn(key)] = new ValuePair(key,value)// name : {key:name,value:'Rick'}
        return true
      }
      return false
    }
    get (key) {
      const valuePair = this.table[this.toStrFn(key)]
      return valuePair === null ?  undefined : valuePair.value
    }
    keyValues() {
      return Object.values(this.table)
    }
    keys() {
      return this.keyValues().map(valuePair => v.key)
    }
    values() {
      return this.keyValues().map(valuePair => v.value)
    }
    // 和forEach方法一样，接收一个callback，由用户传递
    forEach(callback) {
      // 获取所有的value
      const values = this.keyValues()
      // 遍历value
      for (let i = 0; i < values.length; i++) {
        // 执行用户传入的回调函数
        const result = callback(values[i].key,values[i].value)
        // 如果用户传入的执行结果返回了false，那么中断当前的操作
        if (result == false) {
          break
        }
      }
    }
    clear () {
      return this.table = {}
    }
    size () {
      return Object.keys(this.table).length
    }
    isEmpty () {
      return this.size() === 0
    }
    toString () {
      if (this.isEmpty()) {
        return 
      }
      const valuePair = this.keyValues()
      let str = `${valuePair[0].toString()}`
      for (let i = 0; i < valuePair.length; i++) {
        str = `${str},${valuePair[i].toString()}`
      }
      return str
    }
  }
  //#endregion
  // 创建图的骨架Graph类
  class Graph {
    constructor (isDirected = false) {
      this.isDirected = isDirected // 表示是否有向,默认false为无向
      this.vertices = [] // 使用数组来存储图中所有顶点的名字
      this.adjList = new Dictionary() // 之前第八章的字典，主要来存储邻接表，顶点为key，邻边顶点作为值
    }
    // 向当前的图中添加一个新的顶点，图实例化之后是空的
    addVertex(v) { // v是当前要添加的顶点
      if (!this.vertices.includes(v)) { // 不包含在图中
        this.vertices.push(v) // 添加到当前的图里面
        this.adjList.set(v,[]) // 设置当前顶点的邻边为空数组
      }
    }
    // 连接图中的两个顶点
    addEdge(v,w) { // v，w是两个顶点，由v到顶点w
      if (!this.adjList.get(v)) { // 检测v是否在图中，不存在添加
        this.addVertex(v)
      }
      if (!this.adjList.get(w)) { // 检测w是否在图中，不存在添加
        this.addVertex(w)
      }
      // 因为是由顶点v到w所以，将w加入到v的邻边
      this.adjList.get(v).push(w) // 从邻接表里面获取到v顶点的邻边数组，将w加入
      if (!this.isDirected) { // 没有方向的话，互为邻边，如果有方向，则为单向的邻边
        this.adjList.get(w).push(v)
      }
    }
    // 返回顶点列表数组，存储了所有的顶点
    getVertices() {
      return this.vertices
    }
    // 返回图邻接表，里面是字典键值对
    /**
     * v顶点:[存储的邻边1，存储的邻边2]
    */
    getAdjList() {
      return this.adjList
    }
    // 返回邻接表
  }
  // 标记当前节点的状态
    const Colors = {
    WHITE:0, // 完全没有被访问
    GERY:1, // 被发现但是没有被访问
    BLACK:2 // 被发现并且已经被访问
  }
  // vertices 顶点，接受顶点数组，然后设置为未访问
  const initializeColor = vertices => {
      const color = {}
      for (let i = 0; i < vertices.length; i++) {
          color[vertices[i]] = Colors.WHITE
      }
      return color
  }
  
  // 广度优先搜索
  // 图示算法，https://www.cnblogs.com/huansky/p/12826857.html
  const breadthFirstSearch = (graph/**图*/, startVertex/*开始顶点*/, callback) => {
    const vertives = graph.getVertices()
    const adjList = graph.getAdjList()
    const color = initializeColor(vertives) // 将图中的节点全部初始化为白色
    const queue = new Queue() //初始化一个队列，将顶点加入到其中
    queue.enqueue(startVertex) // 将第一个顶点加入到队列中

    while(!queue.isEmpty()) {
      const u = queue.dequeue() // 从queue队列中取出第一个
      const neighbors = adjList.getAdjList() // 获取到这个点的邻边数组
      color[u] = Colors.GERY // 标记为灰色，表示被发现但是没访问
      for (let i = o; i < neighbors.length; i++) { // 遍历邻边数组
        const w = neighbors[i]
        if (color[w] === Colors.WHITE) { //如果当前节点是白色没有被访问过
          color[w] = Colors.GERY // 标记为灰色，表示被发现但是没访问
          queue.enqueue(w) // 加入到queue队列
        }
      }
      color[u] = Colors.BLACK // 上面已经遍历了点的邻边，表示已经被发现并且被访问
      if (callback) {
        callback(u)
      }
    }
  }

深度优先搜索

图示算法过程： https://www.cnblogs.com/huansky/p/12821889.html
使用栈数据结构,会从第一个顶点开始遍历，沿着路径纵深访问。换而言之，先深度，后广度的访问顶点。

// 深度优先搜索，栈数据结构
  // https://www.cnblogs.com/huansky/p/12821889.html
  const depthFirstSearch = (graph, callback) => {
    const vertives = graph.getVertices()
    const adjList = graph.getAdjList()
    const color = initializeColor(vertives) // 将图中的节点全部初始化为白色
    for (let i = 0; i < vertices.length; i++) {
      if (color[vertives[i]] === Colors.WHITE) {
        depthFirstSearchVisit(vertives[i], color, adjList, callback) // 从图中取出一个点开始遍历
      }
    }
    const depthFirstSearchVisit = (u, color, adjList, callback) => {
      color[u] = Colors.GERY // 表示已经发现
      if (callback) {
        callback(u)
      }
      const neighbors = adjList.get(u) // 获取到邻边
      for (let i = 0; i < neighbors.length; i++) {
        let w = neighbors[i]
        if (color[w] === Colors.WHITE) {
          // 不断纵深遍历，深度优先
          depthFirstSearchVisit(w,color,adjList,callback)
        }
      }
      color[u] = Colors.BLACK
    }
  }