Breadth first search algorithm :param graph: :param start_vertex: :return:
(graph, start_vertex)
| 6 | |
| 7 | |
| 8 | def search(graph, start_vertex): |
| 9 | """ |
| 10 | Breadth first search algorithm |
| 11 | |
| 12 | :param graph: |
| 13 | :param start_vertex: |
| 14 | :return: |
| 15 | """ |
| 16 | |
| 17 | # Take a list for storing already visited vertexes |
| 18 | if start_vertex not in graph or graph[start_vertex] is None or graph[start_vertex] == []: |
| 19 | return None |
| 20 | |
| 21 | # create a list to store all the vertexes for BFS and a set to store the visited vertices |
| 22 | visited, queue = set(), [start_vertex] |
| 23 | |
| 24 | while queue: |
| 25 | vertex = queue.pop(0) |
| 26 | if vertex not in visited: |
| 27 | visited.add(vertex) |
| 28 | queue.extend(graph[vertex] - visited) |
| 29 | return visited |
| 30 | |
| 31 | |
| 32 | # TODO: Are these necessary? |