Breadth-first search python
def bfs(graph, vertex):
stack = []
distances = {}
distance = 0
if isinstance(graph, dict):
visited = {key: False for key in graph.keys()}
children = graph[vertex].keys()
if isinstance(graph, list):
visited = [False] * len(graph)
children = graph[vertex]
for child in children:
distances[child] = {
'distance': distance + 1,
'predecessor': vertex
}
stack.append(child)
while stack:
vertex = stack.pop()
if not visited[vertex]:
visited[vertex] = True
if isinstance(graph, dict):
children = graph[vertex].keys()
if isinstance(graph, list):
children = graph[vertex]
for child in children:
if not visited[child]:
distance = distances[vertex]['distance'] + 1
distances[child] = {
'distance': distance,
'predecessor': vertex
}
stack.append(child)
return distances
