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

DFS BFS算法比较

分类: golang编程 | 浏览: 364

最近在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演示。遍历一颗二叉树，队列使用数组，这是为了实现而实现，不用深究。

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

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

总结：

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

相关文章