第 5 题：介绍下深度优先遍历和广度优先遍历，如何实现？ #9
Comments
|
概念上我觉得没啥问题，具体在业务上有啥应用的地方吗（尤其是前端）？ 2.14补充 |
图图是一种复杂的非线性结构，它由边（边Edge）和点（顶点Vertex）组成。一条边连接的两个点称为相邻顶点。 G = (V, E)图分为：
本文探讨的是无向图 图的表示图的表示一般有以下两种：
创建图下面声明图类，Vertex 用数组结构表示，Edge 用 map结构表示 function Graph() {
this.vertices = [] // 顶点集合
this.edges = new Map() // 边集合
}
Graph.prototype.addVertex = function(v) { // 添加顶点方法
this.vertices.push(v)
this.edges.set(v, [])
}
Graph.prototype.addEdge = function(v, w) { // 添加边方法
let vEdge = this.edges.get(v)
vEdge.push(w)
let wEdge = this.edges.get(w)
wEdge.push(v)
this.edges.set(v, vEdge)
this.edges.set(w, wEdge)
}
Graph.prototype.toString = function() {
var s = ''
for (var i=0; i<this.vertices.length; i++) {
s += this.vertices[i] + ' -> '
var neighors = this.edges.get(this.vertices[i])
for (var j=0; j<neighors.length; j++) {
s += neighors[j] + ' '
}
s += '\n'
}
return s
}测试： var graph = new Graph()
var vertices = [1, 2, 3, 4, 5]
for (var i=0; i<vertices.length; i++) {
graph.addVertex(vertices[i])
}
graph.addEdge(1, 4); //增加边
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
console.log(graph.toString())
// 1 -> 4 3
// 2 -> 3 5
// 3 -> 1 2
// 4 -> 1
// 5 -> 2测试成功 图的遍历两种遍历算法：
深度优先遍历（DFS）深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。 简单的说，DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。 DFS 可以产生相应图的拓扑排序表，利用拓扑排序表可以解决很多问题，例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。 注意：深度DFS属于盲目搜索，无法保证搜索到的路径为最短路径，也不是在搜索特定的路径，而是通过搜索来查看图中有哪些路径可以选择。 步骤：
实现： Graph.prototype.dfs = function() {
var marked = []
for (var i=0; i<this.vertices.length; i++) {
if (!marked[this.vertices[i]]) {
dfsVisit(this.vertices[i])
}
}
function dfsVisit(u) {
let edges = this.edges
marked[u] = true
console.log(u)
var neighbors = edges.get(u)
for (var i=0; i<neighbors.length; i++) {
var w = neighbors[i]
if (!marked[w]) {
dfsVisit(w)
}
}
}
}测试： graph.dfs()
// 1
// 4
// 3
// 2
// 5测试成功 广度优先遍历（BFS）广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现BFS BFS从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层 步骤：
实现： Graph.prototype.bfs = function(v) {
var queue = [], marked = []
marked[v] = true
queue.push(v) // 添加到队尾
while(queue.length > 0) {
var s = queue.shift() // 从队首移除
if (this.edges.has(s)) {
console.log('visited vertex: ', s)
}
let neighbors = this.edges.get(s)
for(let i=0;i<neighbors.length;i++) {
var w = neighbors[i]
if (!marked[w]) {
marked[w] = true
queue.push(w)
}
}
}
}测试： graph.bfs(1)
// visited vertex: 1
// visited vertex: 4
// visited vertex: 3
// visited vertex: 2
// visited vertex: 5测试成功 本文始发于我的博客：深度优先遍历与广度优先遍历 |
前端确实很少涉及算法。 这个我也只在做小游戏的时候有用到过 |
|
|
@atheist1 |
|
@caihg 我也是这样想的 |
这其实是和公司的具体业务相关的，我们公司把在业务层背后抽象了一套树形结构的领域对象模型，整个项目里少不了折腾树的递归，这时候发现熟练掌握深度遍历和广度遍历就十分有用了。 |
|
@atheist1 宽搜还是写 queue 吧，stack 歧义太严重了 |
|
|
|
写得非常好了，我之前也了解过这两个东西，@atheist1 ，代码通俗易懂，答案简单直观，非常棒 |
|
generator +Interator接口实现深度遍历 |
问下大佬，有个旧的json 格式转成新的json格式 var old ={ var new =[ ] |
|
|
深度优先：找到一个节点后，把它的后辈都找出来，最常用递归法。 |
为啥是广度的啊？deepTraversal3 不是把当前节点的所有子节点遍历出来之后，在遍历下一个同胞节点吗？ |
感谢楼主的回答，了解到了深度遍历和广度遍历区别，小白把代码放在codepen实现了一遍。https://codepen.io/valleylmh/pen/EBBrWg |
二叉树var myTree = {
val: 6,
left: {
val: 5,
left: {
val: 4
},
right: {
val: 3
}
},
right: {
val: 2,
right: {
val: 1
}
}
}广度优先遍历 BFS思路是利用队列，从根节点开始，依次将左节点、右节点push进数组。 function bfs (tree) {
var queue = [tree]
var res = []
var count = 0
while (queue[count] && queue[count].val) {
res.push(queue[count].val)
var left = queue[count].left
var right = queue[count].right
if (left) {
queue.push(left)
}
if (right) {
queue.push(right)
}
count++
}
return res
}深度优先遍历 DFS思路是利用栈，从根节点开始，依次将右、左节点入栈。 // 非递归版本
function dfs (tree) {
var stack = [tree]
var res = []
while (stack.length) {
var node = stack.pop()
res.push(node.val)
var left = node.left
var right = node.right
if (right) stack.push(right)
if (left) stack.push(left)
}
return res
} |
深拷贝感觉是用到了深度优先, 广度优先,我还没写过...我得研究下 |
从掘金的广度深拷贝问题过来的，结果全是在聊遍历，自己试着实现了一下广度拷贝，不知道有没有更好的方式。 const isArray = (a)=>{Array.isArray(a)};
const isObject = (o)=>Object.prototype.toString.call(o) === '[object Object]';
/**
* 广度优先深拷贝，借助队列实现，每个子节点入队列时，记录下它的新父节点以及他的key
*/
const bfsCopy = (src)=>{
const queue = [];
// 入队列操作
const inQueue = (o,parent) => {
for(let key in o){
queue.push({
parent, // 新的父节点
key, // 子节点的key
node: o[key] // 子节点
})
}
}
if(isArray(src) || isObject(src)){
const root = isArray(src) ? [] : {};
// 将根节点的子节点入队列
inQueue(src,root);
// 开始遍历队列
while(queue.length !== 0){
// 取出队头元素
const { parent, key , node } = queue.shift();
if(isArray(node) || isObject(node)){
const r = isArray(node) ? [] : {};
parent[key] = r;
inQueue(node,r)
}else{
parent[key] = node;
}
}
return root;
}
return src;
} |
这个是深度优先的，你看看它最后的循环，是从末尾开始，也就是说，再下一次循环进来的时候，每次出栈都是从后面最后一个开始[其实已经到了子节点的范畴了】，[(当前节点的子节点是被放在栈的后面） |
|
感觉广度优先遍历使用的stack 应该使用queue 更合适吧 就是先push进去的 先shift(）取出来 放在nodes里 |
所有的方法都缺少对 node.chilren的非空判断，如果对象没有children属性则会报错 |
|
深度优先遍历
|
|
宽度优先遍历 和 深度优先遍历 是 深度优先遍历： 从根节点开始，沿着树的深度遍历树的节点，尽可能深的搜索树的分支。沿着一条可能的路径一直往下走，深入到不能深入为止。【可以纵向优先搜索】 宽度优先遍历： 从根节点开始，沿着树的宽度遍历树的节点。横向一层(level)的去遍历。 一楼大兄弟的html代码： <div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1">
a
</div>
<div class="child-1-1-2">
b
</div>
</div>
<div class="child-1-2">
<div class="child-1-2-1">
c
</div>
</div>
<div class="child-1-3">
d
</div>
</div>
<div class="child-2">
<div class="child-2-1">
e
</div>
<div class="child-2-2">
f
</div>
</div>
<div class="child-3">
<div class="child-3-1">
g
</div>
</div>
</div>深度优先遍历 - 递归 var dfs_recursive = function(root, res = []){
res.push(root)
for (let item of root.children) {
dfs_recursive(item, res)
}
return res
}
console.log('1------------->>', dfs_recursive(root))深度优先遍历 - stack 先进后出 【push(item) -> pop】 或者 [unshift(item) -> shift()] var dfs_stack = function(root) {
const res = []
const stack = []
stack.push(root)
while (stack.length != 0) {
let item = stack.pop()
res.push(item)
for (let i = item.children.length - 1; i >= 0; i--) {
stack.push(item.children[i])
}
}
return res
}
console.log('2------------->>', dfs_stack(root))广度优先遍历 - queue 先进先出[push(item) -> shift()] 或者[unshift(item) -> pop()] var bfs_queue = function(root) {
const res = []
const queue = []
queue.push(root)
while (queue.length != 0) {
let currentLevelLength = queue.length
for (let i = 0 ; i < currentLevelLength; i++) {
let item = queue.shift()
res.push(item)
for (let j = 0; j < item.children.length; j++) {
queue.push(item.children[j])
}
}
}
return res
}
console.log('3------------->>', bfs_queue(root)) |
|
深度遍历 广度遍历 测试代码 |
|
我看大家广度优先都用两个数组做，其实用一个就可以了 ，利用for循环每次计算length的特性 ` |
|
我举个通俗的例子 深度优先遍历就是你拿起第一个杯子，喝光水，然后再拿起下一个杯子，喝光，一直到最后一个杯子。 广度优先遍历就是你从第一个杯子开始，每个杯子挨个都喝一口，然后又重头开始挨个喝一口，一直到全部喝完为止。 是这样吧？ |
遍历树型结构对象啊 |
const data = [{
name: 'a',
children: [{
name: 'a1',
children: [{
name: 'a11'
}, {
name: 'a12'
}]
}, {
name: 'a2',
children: [{
name: 'a21'
}, {
name: 'a22'
}]
}, {
name: 'a3',
children: [{
name: 'a31'
}, {
name: 'a32'
}]
}, ],
}, {
name: 'b',
children: [{
name: 'b1',
children: [{
name: 'b11'
}, {
name: 'b12'
}]
}, {
name: 'b2',
children: [{
name: 'b21'
}, {
name: 'b22'
}]
}, {
name: 'b3',
children: [{
name: 'b31'
}, {
name: 'b32'
}]
}, ],
}];
let result = [];
// 深度遍历
function deep(ary) {
for (const val of ary) {
result.push(val.name);
if (Array.isArray(val.children)) {
deep(val.children);
}
}
return result.join(',');
}
// const str = deep(data);
// 广度遍历
function bfs(ary) { // 对比了下楼上的,我发现我这运行效率有点低,233333
let quee = [];
for (let i = 0; i < ary.length; i++) {
result.push(ary[i].name);
if (Array.isArray(ary[i].children)) {
quee.push(...ary[i].children);
if (i === ary.length - 1) {
bfs(quee);
}
}
}
return result.join(',');
}
const str = bfs(data);
console.log(str); |
第二个广度和第一个不是一样的嘛 |
没毛病的，循环是倒序。就是深度 |
获取项不一样 一个用到了pop 一个用shift |
DFS 可以用在查找两个 dom 节点的相同祖先节点 |
|
数组扁平化 |
|
我在业务中有用到过： |
|
附上结果图：
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
const root = new TreeNode(
1,
new TreeNode(2, null, new TreeNode(4)),
new TreeNode(3, new TreeNode(5))
);
console.log(root);
function dfs(root) {
if (!root) return;
console.log(root.val);
dfs(root.left);
dfs(root.right);
}
function bfs(root) {
if (!root) return
const queue = []
queue.push(root)
while(queue.length){
let len = queue.length
for(let i = 0; i < len; i++){
let cur = queue.shift()
console.log(cur.val);
if(cur.left) queue.push(cur.left)
if(cur.right) queue.push(cur.right)
}
}
}
console.log("------------------dfs-----------------");
dfs(root);
console.log("------------------bfs-----------------");
bfs(root); |
这个打印出来是深度优先哟，实践一下再说，别误导了 |
|
存收到，谢谢！
|
|
给sisterAn的回复加上了一些配图,方便理解 图图是一种复杂的非线性结构,他由边(Edge)和点(Vertex)组成. 图分为:
本文探讨的是无向图 图的表示图的表示一般有以下两种:
创建图Vertex用数组结构表示,Edge用[[Set、Map、WeakSet 和 WeakMap 的区别#字典 Map|map]]结构表示（因为“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键。） function Graph() {
this.vertices = []; //顶点集合
this.edges = new Map(); //边集合
}
//添加顶点方法
Graph.prototype.addVertex = function (v) {
this.vertices.push(v);
this.edges.set(v, []);
};
//添加边方法
Graph.prototype.addEdge = function (v, w) {
if (v === w) return;
let vEdge = this.edges.get(v);
vEdge.push(w);
let wEdge = this.edges.get(w);
wEdge.push(v);
this.edges.set(v, vEdge);
this.edges.set(w, wEdge);
};
// 打印出顶点和与其相邻的顶点
Graph.prototype.toString = function () {
let s = "";
for (const vertex of this.vertices) {
s += vertex + " -> ";
const neighbors = this.edges.get(vertex);
for (const neighbor of neighbors) {
s += neighbor + " ";
}
s += "\n";
}
return s;
};测试:
// 测试
const graph = new Graph();
const vertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
for (v of vertices) {
graph.addVertex(v);
}
graph.addEdge("A", "B");
graph.addEdge("A", "F");
graph.addEdge("B", "C");
graph.addEdge("B", "I");
graph.addEdge("B", "G");
graph.addEdge("C", "D");
graph.addEdge("C", "I");
graph.addEdge("D", "E");
graph.addEdge("D", "H");
graph.addEdge("D", "G");
graph.addEdge("D", "I");
graph.addEdge("E", "F");
graph.addEdge("E", "H");
graph.addEdge("F", "G");
graph.addEdge("H", "G");
console.log(graph.toString());
// A -> B F
// B -> A C I G
// C -> B D I
// D -> C E H G I
// E -> D F H
// F -> A E G
// G -> B D F H
// H -> D E G
// I -> B C D 测试成功 图的遍历两种遍历算法：
深度优先遍历(DFS)深度优先遍历（Depth-First-Search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。 简单的说，DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。 DFS 可以产生相应图的拓扑排序表，利用拓扑排序表可以解决很多问题，例如最大路径问题。一般用堆数据结构来辅助实现DFS算法。 注意：深度DFS属于盲目搜索，无法保证搜索到的路径为最短路径，也不是在搜索特定的路径，而是通过搜索来查看图中有哪些路径可以选择。 步骤
实现Graph.prototype.dfs = function () {
// 原例子用的是数组 因为它存的顶点是number类型
// 但我这边是string 所以使用map 同时也兼容number类型的情况
const marked = new Map();
const edges = this.edges;
for (const vertex of this.vertices) {
if (!marked.get(vertex)) {
dfsVisit(vertex);
}
}
function dfsVisit(u) {
marked.set(u, true);
console.log(u);
const neighbors = edges.get(u);
for (const w of neighbors) {
if (!marked.get(w)) {
dfsVisit(w);
}
}
}
};测试
graph.dfs();
// A
// B
// C
// D
// E
// F
// G
// H
// I广度优先遍历(BFS)广度优先遍历（Breadth-First-Search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，BFS 同样属于盲目搜索，一般用队列数据结构来辅助实现BFS BFS从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层 步骤
实现Graph.prototype.bfs = function (v) {
const queue = [];
const marked = new Map();
marked.set(v, true);
queue.push(v); //添加到队尾
while (queue.length > 0) {
const s = queue.shift(); //从队首移除
if (this.edges.has(s)) {
console.log(s);
}
const neighbors = this.edges.get(s);
for (const w of neighbors) {
if (!marked.get(w)) {
marked.set(w, true);
queue.push(w);
}
}
}
};测试
graph.bfs("A");
// A
// B
// F
// C
// I
// G
// E
// D
// H |
在做后台管理系统的时候，遇到了这样的需求：左侧做成无限级目录，右侧上方面包屑要显示对应的路径。 这个时候有两种方案：
|
|
存收到，谢谢！
|
|
菜狗子前端分享一下自己的总结，如有不足欢迎指出！ dfs和bfs导览： 图图的构造函数和方法//撰写图的构造函数和方法
function Graph() {
this.vertices = [];
this.edges = new Map();
}
Graph.prototype.addVertex = function (v) {
this.vertices.push(v);
this.edges.set(v, []); //给顶点set一个边集合（空）
};
Graph.prototype.addEdge = function (v, w) {
if (v === w) return;
//分别拿到v w 的相邻点集合 push进去 不需要再set
this.edges.get(v).push(w);
this.edges.get(w).push(v);
};图的dfs
//Depth First Search
Graph.prototype.dfs = function () {
//图的dfs需要一个map来存放traversal过的顶点
//因为不是树形结构 所以会出现traversal回来的情况
const marked = new Map();
//储存变量方便traversal函数使用 因为this是undefined
const edges = this.edges;
//遍历所有的点
for (const vertex of this.vertices) {
//若没有被traversal过 则traversal它
if (!marked.get(vertex)) {
traversal(vertex);
}
}
//函数声明会提升 但是const定义变量不会提升
//所以edges要在前面定义好了
function traversal(u) {
marked.set(u, true);
//操作
console.log(u, "-dfsTraversal");
const neighbors = edges.get(u);
//** 一直往下遍历
for (const w of neighbors) {
if (!marked.get(w)) {
traversal(w);
}
}
}
};此外还可以使用入栈出栈的方法，见下文 图的bfs
//Breadth First Search
//需要一个起始节点
Graph.prototype.bfs = function (v) {
if (!this.edges.has(v)) {
console.log("需要一个正确的起始节点");
return;
}
//需要维护一个队列
const queue = [];
const marked = new Map();
//添加到队尾
queue.push(v);
//入队marked设置为true
marked.set(v, true);
while (queue.length > 0) {
//remove first element 出队
const u = queue.shift();
//操作
console.log(u, "-bfsTraversal");
//需要将它的neighbor中未被遍历过的点加入队列
const neighbor = this.edges.get(u);
for (const w of neighbor) {
//保证队列里都是未被遍历过的顶点
if (!marked.get(w)) {
//**只要进入了队列 就当做被遍历过 marked中设置为true
//这样可以避免无限向队列里添加点
marked.set(w, true);
queue.push(w);
}
}
}
};树
DOM树长这个样子： <div class="parent">
<div class="child-1">
<div class="child-1-1">
<div class="child-1-1-1"></div>
<div class="child-1-1-2"></div>
</div>
<div class="child-1-2">
<div class="child-1-2-1"></div>
</div>
<div class="child-1-3"></div>
</div>
<div class="child-2">
<div class="child-2-1"></div>
<div class="child-2-2"></div>
</div>
<div class="child-3">
<div class="child-3-1"></div>
</div>
</div>
<script>
const node = document.querySelector(".parent");
...
</script>要求：按顺序打印出遍历的元素。 DOM节点的dfs递归
// 树的dfs不需要存marked标记 自上而下的递归就行了（因为不可能往回走）
const dfs1 = node => {
if (node != null) {
for (const child of node.children) {
//操作
console.dir(child);
//递归
dfs1(child);
}
}
};栈
//不使用递归
const dfs2 = node => {
const stack = [];
if (node !== null) {
stack.push(node);
//while(stack.length)也行
while (stack.length > 0) {
//后进(push)先出(pop)
const item = stack.pop();
//操作
console.dir(item, "stack");
const children = item.children;
//循环入栈children
//倒着循环是为了和上述结果保持一致 for of 也可以
for (let i = children.length - 1; i >= 0; i--) {
stack.push(children[i]);
}
}
}
};DOM节点的bfs队列
const bfs = node => {
const queue = [];
if (node != null) {
queue.push(node);
while (queue.length > 0) {
//出队
const item = queue.shift();
//操作
console.dir(item);
const children = item.children;
//子节点入队
for (const child of children) {
queue.push(child);
}
}
}
};栈与队列在dfs和bfs时的区别使用栈和队列时需要一个起始点，进行分解（对于图来说就是分解为相邻的点）
|
and others
第五题问的是深度优先遍历和广度优先遍历，我是从dom节点的遍历来理解这个问题的
html代码
我将用深度优先遍历和广度优先遍历对这个dom树进行查找
深度优先遍历
深度优先遍历DFS 与树的先序遍历比较类似。
假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
输出结果
广度优先遍历
广度优先遍历 BFS
从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
输出结果
ps
仅个人理解，如果有错欢迎大家指出批评，一起进步
The text was updated successfully, but these errors were encountered: