深度優先遍歷，廣度優先遍歷實現對象的深拷貝
- 2019 年 10 月 3 日
- 筆記
深度優先遍歷
深度優先遍歷（Depth-First-Search），是搜索演算法的一種，它沿著樹的深度遍歷樹的節點，儘可能深地搜索樹的分支。當節點v的所有邊都已被探尋過，將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已探尋源節點到其他所有節點為止，如果還有未被發現的節點，則選擇其中一個未被發現的節點為源節點並重複以上操作，直到所有節點都被探尋完成。
簡單的說，DFS就是從圖中的一個節點開始追溯，直到最後一個節點，然後回溯，繼續追溯下一條路徑，直到到達所有的節點，如此往複，直到沒有路徑為止。
DFS和BFS一般是用來解決圖的遍歷的，但是在這裡，既然是前端，我是用DFS和BFS來遍歷DOM樹。
下面採用棧的形式或者遞歸的形式實現：
DOM節點
<div class="parent"> <div class="c-1"> <div class="c-1-1"> </div> <div class="c-1-2"> </div> <div class="c-1-3"> </div> <div class="c-1-4"> </div> <div class="c-1-5"> </div> </div> <div class="c-2"> <div class="c-2-1"> </div> <div class="c-2-2"> </div> <div class="c-2-3"> </div> <div class="c-2-4"> <div class="c-2-4-1"> </div> <div class="c-2-4-2"> </div> <div class="c-2-4-3"> </div> <div class="c-2-4-4"> </div> <div class="c-2-4-5"> </div> </div> <div class="c-2-5"> </div> </div> <div class="c-3"> </div> <div class="c-4"> </div> </div>DFS實現
var node = document.querySelectorAll('.parent')[0]; //遞歸寫法 function DFS1 (node, nodeList = []){ if (node != null){ nodeList.push(node); let children = node.children for(let i = 0; i < children.length; i++){ DFS1(children[i], nodeList) } } return nodeList } let nodeList = DFS1(node); console.log(nodeList); //棧寫法 function DFS2(node){ let nodeList = []; if (node){ //棧 後進先出 let stack = []; stack.push(node); while (stack.length) { let _node = stack.pop(); nodeList.push(_node); let children = _node.children; //這樣寫是從右向左 // for (let i = 0; i < children.length; i++) { // stack.push(children[i]); // } //從左向右 for (let i = children.length-1; i >= 0; i--) { stack.push(children[i]); } } } return nodeList; } let nodeList2 = DFS2(node); console.log(nodeList2);運行結果，上面DFS1和DFS2的結果是一樣的
廣度優先遍歷
廣度優先遍歷（Breadth-First-Search）是從根節點開始，沿著圖的寬度遍歷節點，如果所有節點均被訪問過，則演算法終止，BFS 同樣屬於盲目搜索，一般用隊列數據結構來輔助實現BFS。
還是採用上面的DOM節點。BFS的寫法如下。
程式碼採用隊列的形式實現。
var node = document.querySelectorAll('.parent')[0]; function BFS1(node, nodeList = []) { if (!node){ return; } //隊列 先進先出 var sequeue = []; sequeue.push(node); while (sequeue.length){ var _node = sequeue.shift(); nodeList.push(_node) for(var i = 0; i < _node.children.length; i++){ sequeue.push(_node.children[i]) } } return nodeList } let nodeList = BFS1(node); console.log(nodeList);結果如下
下面採用兩種方式來實現對象深度克隆的實現。
DFS深度克隆
深度克隆要注意兩個問題
1、環狀數據問題：如果一個對象具有環狀對象，比如obj.a.b.c === obj.a，就會使遞歸進入死循環，從而導致爆棧錯誤。
2、邊界處理： 對象中不止原始類型，還存在如函數、Set等數據類型，我們需要一一做處理。下面程式碼只是解決了對函數的複製。
let _toString = Object.prototype.toString; let map = { array: 'Array', object: 'Object', function: 'Function', string: 'String', null: 'Null', undefined: 'Undefined', boolean: 'Boolean', number: 'Number' } function getType(obj){ return _toString.call(obj).slice(8, -1) } function isTypeOf(obj, type){ return map[type] && map[type] === getType(obj) } //深度克隆 //深度優先遍歷 /** * * 解決三個問題 遞歸問題 環狀數據問題 邊界處理（比如函數，Set等） */ const DFSdeepClone = function (obj, visitedArr = []){ let _obj = {}; if (isTypeOf(obj, 'array') || isTypeOf(obj, 'object')){ let index = visitedArr.indexOf(obj); if (index > -1){ _obj = visitedArr[index] } else{ visitedArr.push(obj) for (let key in obj){ _obj[key] = DFSdeepClone(obj[key], visitedArr) } } } else if(isTypeOf(obj, 'function')){ _obj = eval( '(' + obj.toString() + ')')//處理函數 } else{ _obj = obj;//處理原始值 } return _obj; } let testObj = { a: 1, b: { c: 1, d: 2 }, circle: null, e: function() { console.log(1); } } let cloneTestObj = DFSdeepClone(testObj); let cloneTestObj2 = testObj; console.log(cloneTestObj); console.log('經過深度克隆後的更改'); cloneTestObj.b = {};//經過深度克隆後的更改 console.log(cloneTestObj); console.log(testObj); cloneTestObj2.b = {}; //引用的更改 console.log('引用的更改'); console.log(cloneTestObj2); console.log(testObj); //環狀數據 let testCircle = { a: 1, b: { c: 1, d: 2, circle: null, }, e: function() { console.log(1); } } testCircle.b.circle = testCircle.b; cloneTestCircle = DFSdeepClone(testCircle);//不處理環問題是會爆棧的 進入死循環 console.log(cloneTestCircle);BFS深度克隆
let _toString = Object.prototype.toString; let map = { array: 'Array', object: 'Object', function: 'Function', string: 'String', null: 'Null', undefined: 'Undefined', boolean: 'Boolean', number: 'Number' } function getType(obj){ return _toString.call(obj).slice(8, -1) } function isTypeOf(obj, type){ return map[type] && map[type] === getType(obj) } //廣度優先深度克隆， 利用隊列的方式實現 //利用copyObj建立一個與原對象相同的數據結構， 遇到可處理的值（比如原始值，函數，就處理後賦值到相應的節點下） const BFSdeepClone = function (obj, visitedArr = []){ let copyObj = {}; let sequeue = [obj];//進隊列 //同時copyObj也跟著一起進隊列 let copySequeue = [copyObj]; while(sequeue.length){ let _obj = sequeue.shift(); let _copyObj = copySequeue.shift(); if (isTypeOf(_obj, 'array') || isTypeOf(_obj, 'object')){ for(item in _obj){ let val = _obj[item]; if (isTypeOf(val, 'object')){ let index = visitedArr.indexOf(val) if (~index){ //是環形數據 _copyObj[item] = visitedArr[index]; } else{ //新的對象，給copyObj一個對應屬性的空對象 sequeue.push(val); _copyObj[item] = {}; copySequeue.push(_copyObj[item]); visitedArr.push(val); } } else if (isTypeOf(val, 'array')){ sequeue.push(val); _copyObj[item] = []; copySequeue.push(_copyObj[item]) } else if(isTypeOf(val, 'function')){ _copyObj[item] = eval( '(' + val.toString() + ')');//處理函數 } else{ _copyObj[item] = val;//處理原始值 } } } else if(isTypeOf(obj, 'function')){ _copyObj = eval( '(' + _obj.toString() + ')');//處理函數 } else{ _copyObj = _obj;//處理原始值 } } return copyObj } let testObj = { a: 1, b: { c: 1, d: 2 }, circle: null, e: function() { console.log(1); } } let cloneTestObj = BFSdeepClone(testObj); let cloneTestObj2 = testObj; console.log(cloneTestObj); //環狀數據 let testCircle = { a: 1, b: { c: 1, d: 2, circle: null, }, e: function () { console.log(1); } } testCircle.b.circle = testCircle.b; cloneTestCircle = BFSdeepClone(testCircle);//不處理環問題是會爆棧的 進入死循環 console.log(cloneTestCircle); /** * 列印如下 { a: 1, b: { c: 1, d: 2 }, circle: null, e: [Function] } { a: 1, b: { c: 1, d: 2, circle: { c: 1, d: 2, circle: [Circular] } }, e: [Function] } */