View difference between Paste ID: 33BVNLRJ and hyys3LJx
SHOW: | | - or go back to the newest paste.
1
#var visited = [] # List to keep track of visited nodes.
2
var queue = []     #Initialize a queue
3
4
func bfs(visited, graph, node):
5
	var result = []
6
	visited.append(node)
7
	queue.append(node)
8
9
	while queue:
10
		var s = queue.pop_front()
11
		result.append(s)
12
13
		for neighbour in graph[s]:
14
			if not visited.has(neighbour):
15
				visited.append(neighbour)
16
				queue.append(neighbour)
17
	return result
18
19
var graph1 = {
20
	'A' : ['B','C'],
21
	'B' : ['D', 'E'],
22
	'C' : ['F'],
23
	'D' : [],
24
	'E' : ['F'],
25
	'F' : []
26
	}
27
28
var graph2 = {
29
	'0': ['1', '2'],
30
	'1': ['2'],
31
	'2': ['0', '3'],
32
	'3': ['3']
33
	}
34
	
35
var graph3 = { 
36
	0:[1,3,4], 
37
	1:[0,2,4], 
38
	2:[1,6], 
39
	3:[0,4,6], 
40
	4:[0,1,3,5], 
41
	5:[4], 
42
	6:[2,3] 
43
}	
44
45
func test():
46
	print(bfs([], graph1, 'A') == ['A', 'B', 'C', 'D', 'E', 'F'])
47
	print(bfs([], graph2, '2') == ['2', '0', '3', '1'])	
48
	print(bfs([], graph3, 0) == [0, 1, 3, 4, 2, 6, 5])
49
	print(bfs([], graph3, 1) != [0, 1, 3, 4, 2, 6, 5])
50