前端之数据结构（六）图

Augus

关注

发布于: 2 小时前

上一章介绍了树的另一种形态二叉树，并说了递归版的先中后序遍历。

这一章就来介绍一下图这种数据结构。

图

图是网络结构的抽象模型，是一组由边连接的节点。
图可以表示任何二元关系，比如道路、航班......

JS 中没有图，但是可以用 Object 和 Array 构建图。
图的表示法：邻接矩阵、邻接表、关联矩阵......

图的表示法

如下图：

邻接矩阵

用邻接矩阵可以如下表示：

每两个交叉点为 1 的，就代表这两个点链接。

邻接表

用邻接表可以如下表示：

每个点代表相应的 key ，而每个 key 所包含的点，就是它们相连的点。

图的常用操作

深度优先遍历：尽可能深的搜索图的分支。
广度优先遍历：先访问离根节点最近的节点。

下图

通过代码表示如下：

const graph = {    0: [1, 2],    1: [2],    2: [0, 3],    3: [3]}

复制代码

深度优先遍历

访问根节点
对根节点的挨个进行深度优先遍历。

通过如下代码进行深度优先遍历：

const visited = new Set()const dfs = (node) => {    console.log(node);    visited.add(node)    graph[node].forEach(c => {        if (!visited.has(c)) {            dfs(c)        }    })}dfs(2)// 2 0 1 3

复制代码

广度优先遍历

新建一个队列，把根节点入队。
把队头出队并访问。
把对头的没访问过的相邻节点入队。
重复第二三步，直到队列为空。

通过如下代码进行广度优先遍历：

const visited = new Set()const q = [2]visited.add(2)while (q.length) {    const node = q.shift()    console.log(node);    graph[node].forEach(c => {        if (!visited.has(c)) {            q.push(c)            visited.add(c)        }    })}
// 2 0 3 1

复制代码

End~~~

发布于: 2 小时前阅读数: 3

Augus

关注

爱瞎搞的软件开发工程师 2021.06.10 加入

某摸鱼集团

发布

暂无评论

创作场景

前端之数据结构（六）图

图

图的表示法

邻接矩阵

邻接表

图的常用操作

深度优先遍历

广度优先遍历

Augus

评论