dfs.go

package main

import "github.com/sirupsen/logrus"

func main() {
	Init()
	ProcessNodes()

	DFS(nodes[0])
}



type Node struct {
	Id int `json:"id"`
	Name string `json:"name"`
	Left int `json:"left"`
	Right int `json:"right"`
	Top int `json:"top"`
	Bottom int `json:"bottom"`
}

var (
	neighbours map[int][]int = map[int][]int{}
	nodes []Node = []Node{}
)

func Init() {
	nodes = []Node {
		{
			Id:      1,
			Name:    "A",
			Top:   	 2,
			Bottom:  3,
			Left:    4,
			Right:   5,
		},

		{
			Id:      2,
			Name:    "B",
			Top:     1,
			Bottom:  7,
			Left:    3,
			Right:   0,
		},

		{
			Id:      3,
			Name:    "C",
			Top:   	 1,
			Bottom:  2,
			Left:    4,
			Right:   0,
		},

		{
			Id:      4,
			Name:    "D",
			Top:   	 1,
			Bottom:  3,
			Left:    5,
			Right:   8,
		},

		{
			Id:      5,
			Name:    "E",
			Top:   	 1,
			Bottom:  4,
			Left:    6,
			Right:   0,
		},

		{
			Id:      6,
			Name:    "F",
			Top:     7,
			Bottom:  5,
			Left:    8,
			Right:   0,
		},

		{
			Id:      7,
			Name:    "G",
			Top:   	 2,
			Bottom:  8,
			Left:    0,
			Right:   0,
		},

		{
			Id:      8,
			Name:    "H",
			Top:   	 4,
			Bottom:  6,
			Left:    0,
			Right:   0,
		},
	}
}

func ProcessNodes() {
	for _, node := range nodes {
		if node.Top != 0 {
			neighbours[node.Id] = append(neighbours[node.Id], node.Top)
		}

		if node.Right != 0 {
			neighbours[node.Id] = append(neighbours[node.Id], node.Right)
		}

		if node.Bottom != 0 {
			neighbours[node.Id] = append(neighbours[node.Id], node.Bottom)
		}

		if node.Left != 0 {
			neighbours[node.Id] = append(neighbours[node.Id], node.Left)
		}
	}
}

func DFS(startingNode Node) {
	Init()
	ProcessNodes()

	seen := map[int]bool{}
	stack := []int{startingNode.Id}

	for len(stack) != 0 {
		var n int
		n, stack = Pop(stack)
		curr := GetById(n, nodes)

		if !seen[curr.Id] {
			seen[curr.Id] = true
			logrus.Infof("Node #%s", curr.Name)
		}

		for _, neighbourId := range neighbours[curr.Id] {
			if !seen[neighbourId] {
				stack = append(stack, neighbourId)
			}
		}
	}
}

func GetById(id int, nodes []Node) Node {
	var node Node

	for _, n := range nodes {
		if n.Id == id {
			node = n
		}
	}

	return node
}


func Pop(arr []int) (int, []int) {
	return arr[len(arr) - 1:][0], arr[0:len(arr)-1]
}