FilesExpand file tree

 main

/

breadth_search_adjacent_list.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (39 loc) · 933 Bytes

 main

/

breadth_search_adjacent_list.py

Top

File metadata and controls

• Code
• Blame

54 lines (39 loc) · 933 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

def define_graph_adjacent_matrix(nodes):

return [[0 for i in range(nodes)] for j in range(nodes)]

def breadth_search(graph):

looked_at = [0]

queue = [0]

got = []

while len(queue) != 0:

item = queue[0]

for node in range(9):

if graph[item][node] == 1 and node not in looked_at:

queue.append(node)

looked_at.append(node)

got.append(str(item) + " - " + str(node))

queue = queue[1:]

return got

graph = define_graph_adjacent_matrix(9)

graph[0][2] = 1

graph[0][3] = 1

graph[0][1] = 1

graph[1][0] = 1

graph[1][2] = 1

graph[1][4] = 1

graph[2][0] = 1

graph[2][1] = 1

graph[2][6] = 1

graph[2][5] = 1

graph[2][3] = 1

graph[3][0] = 1

graph[3][2] = 1

graph[3][6] = 1

graph[4][1] = 1

graph[5][7] = 1

graph[5][2] = 1

graph[6][2] = 1

graph[6][8] = 1

graph[6][3] = 1

graph[7][5] = 1

graph[8][6] = 1

print(breadth_search(graph))