-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.go
64 lines (53 loc) · 1.03 KB
/
bfs.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package grokking_algorithms
import "container/list"
type Graph struct {
Nodes map[string]*Node
}
type Node struct {
Value string
Edges []*Node
}
type Bfs Graph
func (b Bfs) Connected(start string, target string) bool {
startNode, found := b.Nodes[start]
if !found {
return false
}
q := newQueue(startNode)
visitedNodes := make(map[string]struct{})
for q.len() > 0 {
node := q.pop()
if _, visited := visitedNodes[node.Value]; !visited {
if node.Value == target {
return true
}
visitedNodes[node.Value] = struct{}{}
q.pushEdges(node.Edges)
}
}
return false
}
func newQueue(startNode *Node) queue {
l := list.New()
l.PushBack(startNode)
return queue{l}
}
type queue struct {
list *list.List
}
func (q queue) pop() *Node {
element := q.list.Front()
q.list.Remove(element)
return element.Value.(*Node)
}
func (q queue) pushEdges(edges []*Node) {
for _, edge := range edges {
q.push(edge)
}
}
func (q queue) push(edge *Node) {
q.list.PushBack(edge)
}
func (q queue) len() int {
return q.list.Len()
}