DFS and BFS find path using an integer adjacency list. DFS and BFS are examples of decrease and conquer. I'm just studying. :)

bfs_dfs_find.go

package main

import "fmt"

//undirected graph
var graph map[int][]int

func main() {
	
	graph = make(map[int][]int, 6)

	createVertex(1);
	createVertex(2);
	createVertex(3);
	createVertex(4);
	createVertex(5);
	createVertex(6);

	createEdge(1, 2);
	createEdge(1, 3);
	createEdge(2, 4);
	createEdge(2, 5);
	createEdge(5, 6);


	dfs_path_find(1, 5);
	dfs_path_find(1, 7);

	bfs_path_find(4, 1);
	bfs_path_find(5, 1);

}

func bfs_path_find(source int, sink int) int {
	visited := make(map[int]int, 6)
	// https://github.com/ZachOrr/golang-data-structures/blob/master/queue.go
	q :=new(Queue)
	q.Enqueue(source)

	for q.IsEmpty() != true {
		element := q.Dequeue()
		
		if element == sink {
			fmt.Println("found!")
			return 1
		}

		for _, value := range graph[element] {
			if visited[value] == 0 {
				q.Enqueue(value)
				visited[value] = 1
			}
		}
	}

	fmt.Println("not found!")
	return 0
}

func dfs_path_find(source int, sink int) int {
	visited := make(map[int]int, 6)
	// https://github.com/ZachOrr/golang-data-structures/blob/master/stack.go
	stack :=new(Stack)
	stack.Push(source)

	for stack.IsEmpty() != true {
		element := stack.Pop()
		visited[element] = 1
		
		if element == sink {
			fmt.Println("found it!")
			return 1
		}

		for _, adj := range graph[element] {
			if visited[adj] == 0 {
				visited[adj] = 1
				stack.Push(adj)	
			}
		}
	}

	fmt.Println("not found!")
	return 0
}

func createVertex(value int) {
	if graph[value] == nil {
		graph[value] = append(graph[value], value);
	} else {
		fmt.Println("vertex already created.")
	}
}

func createEdge(node1 int, node2 int) {
	graph[node1] = append(graph[node1], node2)
	graph[node2] = append(graph[node2], node1)
}