活学活用 DFS
2021-03-24 本文已影响0人
青叶小小
一、前言
今天小伙伴给我截了个图，吐糟公司的恶心的需求，需要将一个大的、嵌套列表展开（平铺）成一级列表，然后，哼哧哼哧写完后，给我看。不给我看还不要紧，一给我看，我立马小怒，这是干了多年开发写出来的代码么？废话不多说，先上图片：
N级嵌套.jpeg
二、深度优先搜索 DFS（Depth First Search）
如果各位大一学习过《数据结构》，我记得应该是清华大学出版的（当初是个紫色的封面），现在可能已经改了N版。该书我们在学习完二叉树后，就是学习栈、堆，再然后就是学习 DFS / BFS，之后就是图（Graph）。
因为图比较难（分为无向图和有向图），因此，才先学习 DFS / BFS，图的用处很广（小到社区便利设施搭建，大到城市道路规划、高铁站等），因此，掌握了 DFS，至少对理解图是很有用的，而很多算法题，也涉及到 DFS。
那说了这么多，什么是 DFS ？先来看个图：
dfs.png
如果我们要完整的遍历该结构（所有路径，每个节点只能访问一次），方法是：
- A -> B -> E （深度优先）；
- A -> B -> C -> D （广度优先）；
两种优先的思想：
- 深度优先很简单：先沿着一条路遍历下去，直到没有路；
- 广度优先则是：先遍历当前节点的所有子节点（A的子节点就是 B、C、D）；然后，再依次遍历子节点的子节点；
很明显，上面这个图，我们用 DFS 更简单，也更快速：
- A -> B -> E；
- C -> F -> G -> H -> D；
遇到 A时结束；
三、基于 DFS 优化代码逻辑
我们先来通过代码截图，来了解该数据结构：
- projects 是个列表，每个元素都是 sites；
- sites 也是个列表，每个元素都是 countries；
- countries也是列表，每个元素含有 locals 和 currencies；
将列表展开，最终组合为一个列表，每个对象都含有：
[
{
project: project.name,
siteId: site.siteId,
countryCode: country.countryCode,
localCode: local.localCode,
currencyCode: currency.currencyCode,
host: site.host
},
......
]
思想嘛，就是从头开始遍历，一直遍历到叶子节点，即 country，那么简单了，我给出了 DFS 的 demo，并没有帮他去写这段逻辑（不想因为是拿来主义）。
<!DOCTYPE html>
<html>
<head>
<title>test</title>
</head>
<body>
<script type="text/javascript">
// DFS
function combines (obj, kvs = [], list, comb = {}) {
// 如果 kvs 为 0，表明已经到了叶子节点
// 加入到 list 中，返回上一级，继续 DFS
if (kvs.length === 0) {
list.push(Object.assign({}, comb));
return;
}
// 从 kvs 中取出首元素（KV）
const keyAndValue = kvs.shift();
let k = Object.keys(keyAndValue)[0], v = keyAndValue[k];
const data = obj[k];
if (Array.isArray(data)) {
// 深度遍历
for (let i = 0; i < data.length; i ++) {
comb[v] = data[i][v];
combines(data[i], kvs, list, comb);
}
}
// 返回到上一级时，我们需要将该 kv 放回到数组首位置
// 否则上一级的下一个元素遍历时，kvs 就空了（因为 kvs 是索引传递，不是值拷背传递）
kvs.unshift(keyAndValue);
}
// 构造测试数据
var ks = ['project', 'site', 'city'];
function genData (index) {
let list = [];
for (let i = 0; i < 10; i ++) {
var obj = {};
obj[ks[index] + 'Id'] = Math.random();
if (index+1 < ks.length) {
obj[ks[index+1] + 's'] = genData(index+1);
}
list[i] = obj;
}
return list;
}
// 构造大对象，分别嵌套 ks
var o = {projects: genData(0)};
// 平铺成一级列表 list
var list = []
// 将 o 转化为 list
combines(o, [{projects: 'projectId'},{sites: 'siteId'},{citys: 'cityId'}], list)
console.log(list);
</script>
</body>
</html>
当然，该算法只是给了朋友去参考，实际，怎么也得动手稍微修改一个 combines 的 kvs，来满足他自己的需求。
这里的 DFS 还是最简单，最基本的，并没有考虑数据重复后，要『剪枝』的情况，因为，朋友的实际项目不存在构造出来的数据是重复的。
要想真正学习 DFS 并掌握，还是有一定难度的，多看看算法方面的题，多想多练才能逐渐掌握！
