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 |