图

原文链接：https://note.noxussj.top/?source=sifo

什么是图？

图是网络结构的形象模型，是一组由边连贯的节点。图能够示意任何二元关系，比方路线、航班等。在 JavaScript 中没有图，然而能够通过 Object 和 Array 来构建图。

罕用操作

  • 深度优先遍历
  • 广度优先遍历

图的表示法

  • 邻接矩阵
  • 邻接表
  • 关联矩阵
  • ...

邻接矩阵

邻接表

并非仅限于通过对象/数组示意，其余模式也能够。

    {        "A": ["B"],        "B": ["C", "D"],        "C": ["E"],        "D": ["A"],        "E": ["D"]    }

图的深度/广度优先遍历

深度优先遍历

尽可能深的搜寻图的分支。

口诀：
  1. 先拜访根节点
  2. 对根节点的没拜访过的相邻节点挨个进行深度优先遍历（因为相邻节点可能也会指向以后节点）
    const graph = {        A: ['B'],        B: ['C', 'D'],        C: ['E'],        D: ['A'],        E: ['D']    }        const visited = new Set()        const dfs = (n) => {        console.log(n)            visited.add(n)            graph[n].forEach((item) => {            if (!visited.has(item)) {                dfs(item)            }        })    }        dfs('A') // A B C E D
广度优先遍历

先拜访离根节点最新的节点。

口诀：
  1. 新建一个队列，把根节点入队
  2. 把队头出队并拜访
  3. 把队头的没有拜访过的相邻节点入队
  4. 反复第 2、3 步直到队列为空
    const graph = {        A: ['B'],        B: ['C', 'D'],        C: ['E'],        D: ['A'],        E: ['D']    }        const bfs = (head) => {        const visited = new Set()            visited.add(head)            const q = [head]            while (q.length) {            const n = q.shift()                console.log(n)                graph[n].forEach((item) => {                if (!visited.has(item)) {                    q.push(item)                    visited.add(item)                }            })        }    }        bfs('A') // A B C D E

原文链接：https://note.noxussj.top/?source=sifo