Graph DFS and BFS in Go

main.go

package main

import (
	"fmt"
	"testing"
)

type Graph struct {
	Nodes map[string][]string
}

func (g *Graph) TraverseDFSRecursive(start string) []string {
	var visited []string

	var traverse func(start string)
	traverse = func(start string) {
		if isVisited(visited, start) {
			return
		}
		visited = append(visited, start)
		adj := g.Nodes[start]
		for _, n := range adj {
			traverse(n)
		}
	}
	traverse(start)

	return visited
}

func (g *Graph) TraverseDFSIterative(start string) []string {
	var visited []string

	stack := []string{start}
	for len(stack) > 0 {
		n := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if isVisited(visited, n) {
			continue
		}
		visited = append(visited, n)
		adj := g.Nodes[n]
		if len(adj) > 0 {
			stack = append(stack, adj...)
		}
	}

	return visited
}

func (g *Graph) FindLongstPath(start string) []string {
	stack := []string{}
	longestPath := []string{}
	root := start

	var traverse func(start string)
	traverse = func(start string) {
		stack = append(stack, start)
		adj := g.Nodes[start]
		if len(adj) > 0 {
			for _, n := range adj {
				traverse(n)
			}
		} else {
			if len(stack) > len(longestPath) {
				longestPath = stack
			}
			stack = []string{root}
		}
	}

	traverse(start)

	return longestPath
}

func (g *Graph) TraverseBFSRecursive(start string) []string {
	panic("doesn't make sense")
}

func (g *Graph) TraverseBFSIterative(start string) []string {
	var visited []string
	queue := []string{start}
	for len(queue) > 0 {
		n := queue[0]
		queue = queue[1:]
		if isVisited(visited, n) {
			continue
		}
		visited = append(visited, n)
		adj := g.Nodes[n]
		if len(adj) > 0 {
			queue = append(queue, adj...)
		}
	}

	return visited
}

func isVisited(visited []string, node string) bool {
	for _, n := range visited {
		if n == node {
			return true
		}
	}
	return false
}

/*
     1
   2 5  9
  3  6   10
  4  7   11
     8 12
*/
func main() {
	g := Graph{
		Nodes: map[string][]string{
			"1":  {"2", "5", "9"},
			"2":  {"3", "6"},
			"3":  {"4"},
			"4":  {},
			"5":  {"6"},
			"6":  {"7"},
			"7":  {"8"},
			"8":  {},
			"9":  {"10"},
			"10": {"11"},
			"11": {"12"},
			"12": {"8"},
		},
	}

	root := "1"
	path := g.TraverseDFSRecursive(root)
	fmt.Println("DFS recursive:", path)

	path = g.TraverseDFSIterative(root)
	fmt.Println("DFS iterative:", path)

	path = g.TraverseBFSIterative(root)
	fmt.Println("BFS iterative:", path)

	path = g.FindLongstPath(root)
	fmt.Println("Longest path:", path)
}