七叶笔记 » golang编程 » DFS BFS算法比较

DFS BFS算法比较

最近在leetcode上温习算法,在遍历操作的时候经常用到BFS,DFS两种算法。特此记录

DFS:(Depth-First-Search)深度邮箱搜索算法。优先遍历垂直方向上的元素,然后再遍历水平方向上的元素。例如一颗 二叉树 ,对于每一个节点,都会先遍历左子树然后再遍历右子树。

栈实现:

 type Tree struct {
   Val int   
   Type int   
   Left *Tree   
   Right *Tree
}
func dfs(node *Tree) {
   var stack []*Tree   
   node.Type=1   
   stack=append(stack, node)
   for len(stack)>0 {
      element:=stack[0]
      if element.Type==1 {
         // 逻辑  
        
         element.Type=2      
      }

      if element.Left!=nil && element.Left.Type==0 {
         element.Left.Type=1         
         stack=append(stack, element.Left)
         continue      
      }

      if element.Right!=nil && element.Right.Type==0 {
         stack=append(stack, element.Right)
         continue      
      }

      // 逻辑      
        
      // 弹出元素      
      stack=stack[:len(stack)-1]
   }
}  

最近看到一个使用栈实现深度优先算法的,所以模仿使用了一下。使用递归是更简单易懂的。

函数会从先找左节点,存在左节点把节点压入栈里,并把节点元素从白(Type=0)置为灰(Type=1)(防止重复遍历),同时执行逻辑,把当前节点置为黑(Type=2),一直向下遍历。没有左节点后访问右节点,重复操作。

BFS:(Breadth First Search)叫广度优先搜索。优先遍历水平方向上的对象,然后再遍历下一层对象。如此重复遍历所有元素。实现方式也有递归和非递归两种

队列实现

 type Tree struct {
   Val int   
   Left *Tree   
   Right *Tree
}


func bfs(node *Tree) {
   list:=new(List)
   list.add(node)
   
   for list.length()!=0 {
      firstNode:=list.poll()
      // 逻辑      
     if firstNode.Left!=nil {
         list.add(firstNode.Left)
      }
      if firstNode.Right!=nil {
         list.add(firstNode.Right)
      }
   }
}

type List struct {
   element []*Tree
}


func (this *List) add(node *Tree) {
   this.element=append(this.element, node)
}


func(this *List) poll() *Tree {
   if this.length()==0 {
      return nil   
   }
   result:=this.element[0]
   this.element=this.element[1:]
   return result
}


func (this *List) length() int {
   return len(this.element)
}  

这里使用golang演示。遍历一颗二叉树,队列使用数组,这是为了实现而实现,不用深究。

刚开始遍历根节点,然后存入根节点的子节点到队列,然后遍历子节点,存入子节点的子节点到队列。

这样一层一层的完成遍历。达到先水平方向后垂直方向的遍历过程。

总结:

深度优先算法,广度优先算法恰好是不同方向上的遍历方式。用哪种算法,要根据实际的数据结构,比如:热数据集中在根节点附近则使用广度优先算法,热数据集中在左侧或者右侧则使用深度优先算法。

相关文章