Function BreadthFirstSearch

graph/breadthfirstsearch.go:9–28

BreadthFirstSearch is an algorithm for traversing and searching graph data structures. It starts at an arbitrary node of a graph, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Worst-case performance O(|V|+|E|)=O(b^{d})}O(|V|+|

(start, end, nodes int, edges [][]int)

// Worst-case space complexity	 	O(|V|)=O(b^{d})}O(|V|)=O(b^{d}) where |V| is the number of vertices and |E| is the number of edges in the graph and b is the branching factor of the graph (the average number of successors of a node). d is the depth of the goal node.
// reference: https://en.wikipedia.org/wiki/Breadth-first_search
func BreadthFirstSearch(start, end, nodes int, edges [][]int) (isConnected bool, distance int) {
	queue := make([]int, 0)
	discovered := make([]int, nodes)
	discovered[start] = 1
	queue = append(queue, start)
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		for i := 0; i < len(edges[v]); i++ {
			if discovered[i] == 0 && edges[v][i] > 0 {
				if i == end {
					return true, discovered[v]
				}
				discovered[i] = discovered[v] + 1
				queue = append(queue, i)
			}
		}
	}
	return false, 0
}