Go BFS

bfs.go

package main

import "log"

type Node struct {
	val      int
	marked   bool
	children []*Node
}

type Graph struct {
	root *Node
}

type QueueItem struct {
	*Node
	next *QueueItem
}

type Queue struct {
	first, last *QueueItem
}

func (q *Queue) Enqueue(item *Node) {
	qi := &QueueItem{Node: item}
	if q.first == nil {
		q.first = qi
		q.last = qi
		return
	}
	q.last.next = qi
	q.last = qi

	return
}

func (q *Queue) Pop() *QueueItem {
	if q.first == nil {
		return nil
	}
	node := q.first
	q.first = q.first.next
	if q.first == nil {
		q.last = q.first
	}

	return node
}

func (q Queue) IsEmpty() bool {
	return q.last == nil
}

func main() {
	queue := &Queue{}
	graph := makeGraph()

	bfs(queue, graph[0])
}

func bfs(queue *Queue, node *Node) {
	if node == nil {
		return
	}

	queue.Enqueue(node)

	for !queue.IsEmpty() {
		node := queue.Pop()
		visit(node)
		for _, child := range node.children {
			if !child.marked {
				child.marked = true
				queue.Enqueue(child)
			}
		}
	}
}

func visit(qi *QueueItem) {
	log.Println(qi.val)
}

func makeGraph() []*Node {
	zero := &Node{val: 0}
	one := &Node{val: 1}
	two := &Node{val: 2}
	three := &Node{val: 3}
	four := &Node{val: 4}
	five := &Node{val: 5}

	zero.children = []*Node{one, four, five}
	one.children = []*Node{three, four}
	two.children = []*Node{one}
	three.children = []*Node{two, four}

	return []*Node{zero, one, two, three, four, five}
}