Graph traversal algorithms. Made during Fireship video: https://youtu.be/cWNEl4HE2OE

bfs_graph_traversal.go

// Breadth-First Search: check if there are any routes between two points in graph
package main

import (
	"errors"
	"fmt"
)

var airports = [...]Node{"PHX", "BKK", "OKC", "JFK", "LAX", "MEX", "EZE", "HEL", "LOS", "LAP", "LIM"}
var routes = [...]*Edge[Node]{
	{"PHX", "LAX"},
	{"PHX", "JFK"},
	{"JFK", "OKC"},
	{"JFK", "HEL"},
	{"JFK", "LOS"},
	{"MEX", "LAX"},
	{"MEX", "BKK"},
	{"MEX", "LIM"},
	{"MEX", "EZE"},
	{"LIM", "BKK"},
}

func main() {
	adjacencyList := make(Graph[Node], len(airports))

	for _, airport := range airports {
		adjacencyList.AddNode(airport)
	}

	for _, route := range routes {
		adjacencyList.AddEdge(route.from, route.to)
	}

	fmt.Printf("PHX -> BKK: %v\n", HasRouteFrom("PHX", "BKK", adjacencyList))
	fmt.Printf("LAX -> LAP: %v\n", HasRouteFrom("LAX", "LAP", adjacencyList))
	fmt.Printf("OKC -> MEX: %v\n", HasRouteFrom("OKC", "MEX", adjacencyList))
	fmt.Printf("LOS -> PHX: %v\n", HasRouteFrom("LOS", "PHX", adjacencyList))
}

func HasRouteFrom(start, end Node, graph Graph[Node]) bool {
	visitedNodes := make(Set[Node], len(graph))
	toProcess := Queue[Node]{start}

	for toProcess.Len() > 0 {
		node := toProcess.Dequeue()

		if node == end {
			return true
		}

		children := graph[node]
		for _, child := range children {
			if !visitedNodes.Contains(child) {
				toProcess.Enqueue(child)
				visitedNodes.Add(child)
			}
		}
	}

	return false
}

type Node string
type Edge[T any] struct {
	from T
	to   T
}
type Graph[T comparable] map[T][]T

func (g Graph[T]) AddNode(name T) error {
	if _, ok := g[name]; ok {
		return errors.New("node already exists")
	}

	g[name] = make([]T, 0)

	return nil
}

func (g Graph[T]) AddEdge(from, to T) error {
	if _, ok := g[from]; !ok {
		return errors.New("node in 'from' didn't exist")
	}
	if _, ok := g[to]; !ok {
		return errors.New("node in 'to' didn't exist")
	}

	g[from] = append(g[from], to)
	g[to] = append(g[to], from)

	return nil
}

type Queue[T any] []T

func (q *Queue[T]) Len() int {
	return len(*q)
}
func (q *Queue[T]) Enqueue(v T) {
	*q = append(*q, v)
}
func (q *Queue[T]) Dequeue() (v T) {
	v = (*q)[0]
	*q = (*q)[1:]
	return
}

type Set[T comparable] map[T]struct{}

func (s *Set[T]) Add(v T) {
	(*s)[v] = struct{}{}
}
func (s *Set[T]) Remove(v T) {
	delete(*s, v)
}
func (s *Set[T]) Contains(v T) bool {
	_, ok := (*s)[v]
	return ok
}

dfs_graph_traversal.go

// Depth-First Search: register all possible paths
package main

import "fmt"

type Node string
type Edge struct {
	from Node
	to   Node
}
type Graph map[Node][]Node

var airports = [...]Node{"PHX", "BKK", "OKC", "JFK", "LAX", "MEX", "EZE", "HEL", "LOS", "LAP", "LIM"}
var routes = [...]*Edge{
	{"PHX", "LAX"},
	{"PHX", "JFK"},
	{"JFK", "OKC"},
	{"JFK", "HEL"},
	{"JFK", "LOS"},
	{"MEX", "LAX"},
	{"MEX", "BKK"},
	{"MEX", "LIM"},
	{"MEX", "EZE"},
	{"LIM", "BKK"},
}

func main() {
	adjacencyList := make(Graph, len(airports))

	for _, airport := range airports {
		addNode(airport, adjacencyList)
	}

	for _, route := range routes {
		addEdge(route, adjacencyList)
	}

	fmt.Printf("PHX -> BKK: %v\n", GetRouteFrom("PHX", "BKK", adjacencyList))
	fmt.Printf("LAX -> LAP: %v\n", GetRouteFrom("LAX", "LAP", adjacencyList))
	fmt.Printf("OKC -> MEX: %v\n", GetRouteFrom("OKC", "MEX", adjacencyList))
	fmt.Printf("LOS -> PHX: %v\n", GetRouteFrom("LOS", "PHX", adjacencyList))
}

func addNode(name Node, graph Graph) {
	graph[name] = make([]Node, 0)
}

func addEdge(edge *Edge, graph Graph) {
	graph[edge.from] = append(graph[edge.from], edge.to)
	graph[edge.to] = append(graph[edge.to], edge.from)
}

func GetRouteFrom(start, end Node, graph Graph) [][]Node {
	paths := getRouteFrom(start, end, graph, nil, nil)

	for i, p := range paths {
		if p != nil {
			paths[i] = append(paths[i], end)
		}
	}

	return paths
}

func getRouteFrom(start, end Node, graph Graph, visitedNodes []Node, path []Node) [][]Node {
	if visitedNodes == nil {
		visitedNodes = []Node{}
	}
	visitedNodes = append(visitedNodes, start)

	if path == nil {
		path = []Node{}
	}
	path = append(path, start)

	startChildren := graph[start]

	allPaths := [][]Node{}
	for _, child := range startChildren {
		if child == end {
			allPaths = append(allPaths, path)
			visitedNodes = append(visitedNodes, child)
		}

		if !ValueInSlice(child, visitedNodes) {
			if t := getRouteFrom(child, end, graph, visitedNodes, path); t != nil {
				allPaths = append(allPaths, t...)
			}
		}
	}

	return allPaths
}

func ValueInSlice[T comparable](value T, slice []T) bool {
	for _, next := range slice {
		if next == value {
			return true
		}
	}

	return false
}