bfs python

 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
'''
def createm(n):
a = []
for i in range(0, n):
a.append([])
a[i] = list(map(int, input().split()))
return a
def bfs(v):
global n
global a
global p
q = [] #очередь
used = [False] * n
q += [v]
used[v] = 1
while len(q) != 0:
v = q[0]
q.pop(0)
for to in a[v]:
if (not used[to]):
q += [to]
p[to] = v
used[to] = 1
n = int(input())
matr = createm(n)
a = []
for i in range(0, n):
a.append([])
for i in range(0, n):
for j in range(0, n):
if matr[i][j] != 0:
a[i].append(j)
s, f = map(int, input().split())
print(a)
s -= 1
f -= 1
p = [-1] * n
bfs(s)
b = []
b += [f]
while p[f] != -1:
f = p[f]
b += [f]
b.reverse()
if b[0] != s:
print(-1)
else:
if len(b) == 1:
print(0)
exit(0)
print(len(b) - 1)
for k in b:
print(k, end = ' ')
'''