数据结构与算法之图: 图及其深度和广度优先遍历实现 (Typescript版)

本文主要是介绍数据结构与算法之图: 图及其深度和广度优先遍历实现 (Typescript版)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

图

网络结构的抽象模型，是一组由边连接的节点
图可以表示任何二元关系，道路，航班
- 由边连接的节点
- 图中节点多，但是一条边只能连接两个节点
js中没有图，但可以用Objct和Array构建图
图的表示法：临接矩阵，临接表，关联矩阵…
- 临接矩阵表示法：用矩阵表示
  - 比如这个图上有n个节点, A,B,C,…N
  - 我们画出一个矩阵，横纵都是A->N这n个节点
  - 这个矩阵默认全部填充0,
  - 如果A能连接到B,则在这个矩阵中以A为横轴，B为纵轴相交的那个点置为1表示
  - 如果B能连接到C,则在这个矩阵中以B为横轴，C为纵轴相交的那个点置为1表示
  - …
- 邻接表表示法
  - 更形象，更容易理解，如下, 构建一个对象，对象的key是各个节点
  - 各个节点里面都有一个数组，数组中的值就是这些节点中可以连接的节点
```
{A:["B"],B:["C", "D"],C:["E"],D:["A"],E:["D"]
}
```
  - 里面除了用数组表示，还可以用链表来表示
  - 只要能表达清楚节点之间的链接关系，就可以了
图的常用操作
- 深度优先遍历
- 广度优先遍历

深度优先遍历和广度优先遍历

这里有一个图的示例，对其进行深度和广度的优先遍历

// 邻接表表示法
const graph = {0: [1,2],1: [2],2: [0, 3],3: [3]
}

1 ) 深度优先遍历

尽可能深的搜索图的分支
访问根节点
对根节点的没访问过的相邻节点挨个进行深度优先遍历
- 这里相邻节点和树中的children差不多，概念上相似
- 这里，没有访问过的节点(为了不重不漏)是一个重要的限制条件，如果不是这样，会陷入死循环

// 使用上面定义的通用graph变量
const visited = new Set();
const res = [];
// 深度优先遍历函数
const dfs = (n) => {// console.log(n); // 访问当前节点res.push(n); // 访问过的节点存入结果队列中visited.add(n);graph[n].forEach(c => {if(!visited.has(c)) {dfs(c); // 对没有访问过的节点进行递归}})
}dfs(2) // 这里指定一个起始节点2 
console.log(res.toString()); // 2,0,1,3

2 ) 广度优先遍历

先访问离根节点最近的节点
口诀
- 一、新建一个队列，把根节点入队
- 二、把队头出队并访问
- 三、把队头的没访问过的相邻节点入队
- 重复第二、三步，直到队列为空

// 使用上面定义的通用graph变量
const res = []; // 用于存储最终的结果
// 广度优先遍历函数
const bfs = () => {const visited = new Set();visited.add(2); // 起始节点 注意这里结合下面的漏洞，先加入起始点const q = [2]; // 起始节点while(q.length) {const n = q.shift(); // 队首出队// console.log(n); // 访问当前节点res.push(n);// visited.add(n); // 这里不能在这里添加，会有漏洞，会漏掉一些在q里，但没有在visited中的元素，它会逃过限制，重复在q中被添加// 将相邻节点(孩子节点) 存入队列中graph[n].forEach(c => {// 没有访问过，pushif(!visited.has(c)) {q.push(c);visited.add(c); // 将出队元素添加进入集合 这里结合上面注释掉的漏洞，后添加}})}
}bfs();
console.log(res.toString()); // 2,0,3,1