-
Notifications
You must be signed in to change notification settings - Fork 0
/
BFS-explored-key-value.py
58 lines (49 loc) · 1.1 KB
/
BFS-explored-key-value.py
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
def BFS(initalState, goal):
frontier = [initalState]
explored = []
while frontier:
state = frontier.pop(0)
explored.append(state)
if goal == state:
return explored
for neighbor in graph[state]:
if neighbor not in (explored and frontier):
frontier.append(neighbor)
return False
if __name__ == '__main__':
# graph = {
# 'A': ['B', 'C'],
# 'B': ['D', 'E'],
# 'C': ['F', 'G'],
# 'D': ['H', 'I'],
# 'E': ['J', 'K'],
# 'F': ['L', 'M'],
# 'G': ['N', 'O'],
# 'H': [],
# 'I': [],
# 'J': [],
# 'K': [],
# 'L': [],
# 'M': [],
# 'N': [],
# 'O': []
# }
graph = {
'S': ['A', 'B', 'C'],
'A': ['D'],
'B': ['D', 'E', 'G'],
'C': ['E'],
'D': ['F'],
'E': ['F', 'H'],
'F': ['G'],
'H': ['G']
}
# result = BFS('A', 'O')
result = BFS('S', 'G')
if result:
s = 'explored: '
for i in result:
s += i + ' '
print(s)
else:
print('No solution!')