Dimitris Kougioumtzis Blog About technology

Breadth-first search python

Category Python

Posted on April 9, 2018



Breadth-first search python


 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
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

About

My name is Dimitris Kougioumtzis and i work as a Web developer at Rapidbounce Company

Elsewhere