FilesExpand file tree

 master

/

bfs.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

30 lines (26 loc) · 787 Bytes

 master

/

bfs.py

Copy path

Top

File metadata and controls

• Code
• Blame

30 lines (26 loc) · 787 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

# -*-coding: utf-8 -*-

# Author:

from graphs.Graph import Graph

from graphs.Vertex import Vertex

from myQueue import Queue

def bfs(g, start):

start.setDisatance(0)

start.setPred(None)

vertQueue = Queue()

vertQueue.enqueue(start)

while (vertQueue.size() > 0):

currentVert = vertQueue.dequeue()

for nbr in currentVert.getConnections():

if nbr.getColor() == 'white':

nbr.setColor('gray')

nbr.setDisatance(currentVert.getDistance() + 1)

nbr.setPred(currentVert)

vertQueue.enqueue(nbr)

currentVert.setColor('balck')

def traverse(y):

x = y

while (x.getPred()):

print(x.getId())

x = x.getPred()

print(x.getId())

traverse(g.getVertex('sage'))