FilesExpand file tree

master

/

breadth_first_search.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (38 loc) · 1.06 KB

master

/

breadth_first_search.py

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (38 loc) · 1.06 KB

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

"""

Author: OMKAR PATHAK

Created On: 1st August 2017

"""

import inspect

def search(graph, start_vertex):

"""

Breadth first search algorithm

:param graph:

:param start_vertex:

:return:

"""

# Take a list for storing already visited vertexes

if start_vertex not in graph or graph[start_vertex] is None or graph[start_vertex] == []:

return None

# create a list to store all the vertexes for BFS and a set to store the visited vertices

visited, queue = set(), [start_vertex]

while queue:

vertex = queue.pop(0)

if vertex not in visited:

visited.add(vertex)

queue.extend(graph[vertex] - visited)

return visited

# TODO: Are these necessary?

def time_complexities():

"""

Return information on functions

time complexity

:return: string

"""

return "O(V + E) where V = Number of vertices and E = Number of Edges"

def get_code():

"""

easily retrieve the source code

of the function

:return: source code

"""

return inspect.getsource(search)