-
Notifications
You must be signed in to change notification settings - Fork 0
/
BFS_Queue_G2.py
92 lines (75 loc) · 2.57 KB
/
BFS_Queue_G2.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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def BFS(graph, start, end):
visited = set()
expanded = []
queue = [start]
while queue:
path = queue.pop(0)
current = path[-1]
if current not in expanded:
expanded.append(path[-1])
if current not in visited:
visited.add(current)
if current == end:
return path, expanded
neighbours = graph[current]
for j in neighbours:
if j not in visited:
appends = path + j
queue.append(appends)
maps = {'a':0, 'b': 1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6, 'h':7, 'p':8, 'q':9, 'r':10, 's':11 }
def BFS_Matrix(graph, start, goal, list):
visited = set()
expanded = []
queue = [start]
while queue:
path = queue.pop(0)
current = path[-1]
if current not in expanded:
expanded.append(path[-1])
if current not in visited:
visited.add(current)
if current == goal:
return path, expanded
length = len(graph[maps[current]])
for neighbor in range(length):
if neighbor not in visited and graph[maps[current]][neighbor] == 1:
j = [k for k,v in maps.items() if v == neighbor]
if j[0] not in visited:
appends = path + j[0]
queue.append(appends)
graph2 = {
'a': [],
'b': ['a'],
'c': [],
'd': ['b', 'c', 'e'],
'e': ['h', 'r'],
'f': ['c', 'g'],
'g': [],
'h': ['p', 'q'],
'p': ['q'],
'q': [],
'r': ['f'],
's': ['d', 'e', 'p']}
Adj_matrix=[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]]
path, expanded = BFS(graph2,'s','g')
output = [char for char in path]
print("\nThe path of graph 2 through BFS Queue with vertex list is : " + "->".join(output) + "\n")
print("The states expanded with vertex list are:")
print(expanded)
path_AM, expanded_AM = BFS_Matrix(Adj_matrix,'s','g',[])
output1 = [char for char in path]
print("\nThe path of graph 2 through BFS Queue with adjacency matrix is : " + "->".join(output1) + "\n")
print("The states expanded with adjacency matrix are:")
print(expanded)