算法 DFS与BFS-蒲公英云

算法 DFS与BFS

傷城~ 2022-12-20 03:27 253阅读 0赞

一、DFS（深度优先搜索）

DFS: 深度优先遍历DFS与树的先序遍历比较类似。假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点然后依次访问它的所有邻接结点，每次访问一个邻接结点时，以该邻接结点为根结点继续进行DFS，直到结点的所有邻接结点以及其邻接结点的邻接结点都被访问完，才访问下一个邻接结点并进行同样操作，直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

二、BFS（广度优先搜索）

BFS: 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

三、实现

实现以树为例：树是只有一个根节点，且没有回路的图
对图进行访问时要注意进行回路检测

function TreeNode(_val=undefined, _left=null, _right=null){ 
  this.val = _val;
  this.left = _left;
  this.right = _right;
}
// 0
// / \
// 1 2
// / \ / \
// 3 4 5 6
let root = new TreeNode(0);
root.left = new TreeNode(1, new TreeNode(3), new TreeNode(4));
root.right = new TreeNode(2, new TreeNode(5), new TreeNode(6));
// DFS
function dfs1(_root){ 
  // 递归法 前序遍历
  if(_root){ 
    console.log(_root.val);
    dfs1(_root.left);
    dfs1(_root.right);
  }
}
function dfs2(_root){ 
  if(!_root) return;
  // 非递归法 栈
  let stack = [_root];
  while (stack.length > 0){ 
    let item = stack.pop();
    console.log(item.val);
    // 从末尾开始压栈，二叉树就是先压right，再压left
    item.right && stack.push(item.right);
    item.left && stack.push(item.left);
  }
}
// BFS
function bfs1(_root){ 
  if(!_root) return;
  // 队列
  let queue = [_root];
  while(queue.length > 0){ 
    let item = queue.shift();
    console.log(item.val);
    item.left && queue.push(item.left);
    item.right && queue.push(item.right);
  }
}