BFS / DFS

main.go

package main

import (
	"fmt"
)

type Node struct {
	Children []*Node
	ID       int
}

func main() {
	//              1
	//        -------------
	//        |     |     |
	//        2     3     4
	//     -------     -------
	//     |     |     |     |
	//     5     6     7     8
	//  -------
	//  |     |
	//  9     10
	nodes := make(map[int]*Node, 0)
	for i := 1; i <= 10; i++ {
		nodes[i] = &Node{
			ID: i,
		}
	}

	nodes[1].Children = append(nodes[1].Children, nodes[2], nodes[3], nodes[4])
	nodes[2].Children = append(nodes[2].Children, nodes[5], nodes[6])
	nodes[5].Children = append(nodes[5].Children, nodes[9], nodes[10])
	nodes[4].Children = append(nodes[4].Children, nodes[7], nodes[8])

	nodes[1].BreadthFirstSearch()
	fmt.Println("====")
	nodes[1].DepthFirstSearch(nil)

}

func (n *Node) BreadthFirstSearch() {
	visited := make(map[*Node]struct{})
	queue := []*Node{n}

	for len(queue) > 0 {
		current := queue[0]
		queue = append(queue[1:], current.Children...)

		// If we already visited this node, node need to
		// its children. We should deque them.
		_, exists := visited[current]
		if exists {
			queue = queue[:len(queue)-len(current.Children)]
			continue
		}

		// Do something with "current"
		fmt.Println("Processing", current.ID)
		visited[current] = struct{}{}
	}
}

func (n *Node) DepthFirstSearch(visited map[*Node]struct{}) map[*Node]struct{} {
	if visited == nil {
		visited = make(map[*Node]struct{})
	}

	fmt.Println("Processing", n.ID)
	visited[n] = struct{}{}

skipChild:
	for _, child := range n.Children {
		for v := range visited {
			if v == child {
				continue skipChild
			}
		}

		visited = child.DepthFirstSearch(visited)
	}

	return visited
}

// Output:
// Processing 1
// Processing 2
// Processing 3
// Processing 4
// Processing 5
// Processing 6
// Processing 7
// Processing 8
// Processing 9
// Processing 10
// ====
// Processing 1
// Processing 2
// Processing 5
// Processing 9
// Processing 10
// Processing 6
// Processing 3
// Processing 4
// Processing 7
// Processing 8