An Example of Breadth-first and Depth-first Search Algorithms in Go

Tue 20 November 2018 by jmhal

Below is an example of the two classical approaches for traversing a tree, this time written in the Go programming language.

package main

import (
   "fmt"
)

type tree struct {
   value string
   nodes []*tree
}

func main () {
   node7 := tree{value: "node7", nodes: []*tree{}}
   node6 := tree{value: "node6", nodes: []*tree{}}

   node5 := tree{value: "node5", nodes: []*tree{}}
   node4 := tree{value: "node4", nodes: []*tree{}}
   node3 := tree{value: "node3", nodes: []*tree{}}

   node1 := tree{value: "node1", nodes: []*tree{&node3, &node4, &node5}}
   node2 := tree{value: "node2", nodes: []*tree{&node6, &node7}}

   node0 := tree{value: "node0", nodes: []*tree{&node1, &node2}}

   fmt.Println("Breadth First:")
   breadthFirst(nodeInfo, []*tree{&node0})
   fmt.Println()
   fmt.Println("Depth First:")
   depthFirst(nodeInfo, &node0, make(map[*tree]bool))
   fmt.Println()

   return
}

func nodeInfo(node *tree) {
   fmt.Printf(" %s ", (*node).value)
}

func breadthFirst(f func(node *tree), worklist []*tree) {
   seen := make(map[*tree]bool)
   for len(worklist) > 0 {
      nodes := worklist
      worklist = nil
      for _, node := range nodes {
         if !seen[node] {
        f(node)
        seen[node] = true
        worklist = append(worklist, (*node).nodes...)
     }
      }
   }
}

func depthFirst(f func(node *tree), node *tree, visited map[*tree]bool) {
   visited[node] = true
   f(node)
   for _, child := range (*node). nodes {
      if !visited[child] {
         depthFirst(f, child, visited)
      }
   }
}

For testing the algorithms, there is a simple tree in the code. I depict the tree in the picture below:

Tree Example

The expected output should be:

Breadth First:
 node0  node1  node2  node3  node4  node5  node6  node7
Depth First:
 node0  node1  node3  node4  node5  node2  node6  node7

This small example shows a lot of nice features of Go. We can see that function are first order elements (nodeInfo is provided as a parameter to other functions). breadthFirst is iterative, and depthFirst is recursive. We also have a struct with pointers.