首先要知晓一个概念
图的遍历
概念 图的遍历是指从图的某个节点出发，按既定的方式访问图中各个可访问的节点，使每个可访问的节点恰巧被访问一次 方式 深度优先（DFS---Depth First Search）和广度优先(BFS---Breadth First Search)
深度优先和广度优先的概念
- 深度优先：
概念
首先访问出发点V,并将其标记为已访问过，然受依次从v搜索每个相邻的节点w,如果未曾访问过，则以w为新的出发点继续深度优先遍历，若w相邻的n节点无其他相邻节点，则查找w是否有其他相邻节点，当w相邻节点都深度优先的方式遍历完成，则查找v的其他相邻节点，直到所有相邻节点都访问完成终止。
路径
深度优先就是，从初始点出发，不断向前走，如果碰到死路，就往回走一步，尝试另一条路，直至无路可走。这种方法，记住当前节点位置即可。
代码实现
代码语言：javascript复制 //这是帮助方法利用obj 原型方法的toString,获取某个值的type
function getType(obj) {
return Object.prototype.toString.call(obj).slice(8, -1);
}
// 深度优先
function DFSDeepClone(obj, vistied = new WeakMap()) {
var res;
if (getType(obj) === 'Object' || getType(obj) === 'Array') {
if (vistied.has(obj)) {
// 处理重复引用
res = vistied.get(obj);
} else {
res = getType(obj) === 'Object' ? {} : []
Object.keys(obj).forEach(k => {
// 一个一个处理，每一个都会递归下去
res[k] = DFSDeepClone(obj[k], vistied)
})
// 将拷贝过的对象存储到WeakMap结构中，下次再遇到拷贝该对象，直接复用
vistied.set(obj, res)
}
} else if (typeof obj === 'function') {
// 拷贝函数
if (vistied.has(obj)) {
res = vistied.get(obj)
} else {
res = eval(`(${obj.toString()})`)
vistied.set(obj, res);
}
} else {
// 拷贝基本数据类型
res = obj
}
return res
}- 广度优先
概念
广度优先是从初始点开始，把所有相邻一步的节点都走一次，直到相邻节点都走完，再尝试走两步能走到的节点，将所有走两步能到的节点走完后，走三步能到的节点，每次要记录当前所有相邻的节点。
- 结论 深度优先算法占用内存少，但是速度较慢，广度优先算法占用内存多，速度较快
代码实现
代码语言：javascript复制 function BFSDeepClone(obj) {
// 首先处理obj是普通类型或者函数类型的情况，不是数组/不是对象
if (getType(obj) !== 'Object' && getType(obj) !== 'Array') {
if (typeof obj === 'function') {
obj = eval(`(${obj.toString()})`)
}
return obj
}
// 首先要判断拷贝的数据类型，是数组还是对象
let res = getType(obj)==="Object"?{}:[];
// 队列的思想处理，一层一层的处理，处理父级时，会将待处理的子任务入栈，父级任务处理完毕，再处理子级任务，再次产生新的子级任务，插入到队尾
// 源数据队列,遇到引用数据类型会将目标push到队尾
const origin = [obj]
// 拷贝的数据队列,当目标对象的子属性有引用类型，创建同类型的拷贝属性push到队尾，以配合拷贝
const copy = [res]
// 缓存
const vistied = new WeakMap()
while (origin.length) {
// 获取当前要拷贝的对象
const _obj = origin.shift()
// 获取当前要拷贝的类型结构 {} 或者 []
const copyObj = copy.shift()
Object.keys(_obj).forEach(k => {
const item = _obj[k]
if (getType(item) === 'Object' || getType(item) === 'Array') {
if (vistied.has(item)) {
// 如果之前拷贝过该对象，直接使用拷贝后的结果
copyObj[k] = vistied.get(item);
} else {
copyObj[k] = getType(item) === 'Object' ? {} : []
// push待拷贝的子对象到源对象队列
origin.push(item)
// push拷贝的类型结构到目标对象队列W
copy.push(copyObj[k])
// 将拷贝好的结果存到WeakMap结构
vistied.set(item, copyObj[k]);
}
} else if (typeof item === 'function') {
// 函数类型也缓存拷贝结果
if (vistied.has(item)) {
copyObj[k] = vistied.get(item)
} else {
copyObj[k] = eval(`(${item.toString()})`)
vistied.set(item, copyObj[k]);
}
} else {
// 基础类型直接赋值即可
copyObj[k] = item
}
})
}
return res
}
