乐趣区

关于前端:js中的图

jiezi

图

原文链接：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

退出移动版