bfs.py

"""
https://en.wikipedia.org/wiki/Breadth-first_search
"""

import queue


def bfs(graph, root):

    q = queue.Queue()
    root.visited = True
    q.put(root)
    print(root)

    while not q.empty():
        current = q.get()
        for vertex in current.adjacent:
            if vertex.visited:
                continue
            vertex.visited = True
            q.put(vertex)
            print(vertex)


class City(object):
    def __init__(self, name):
        self.name = name
        self.visited = False
        self.adjacent = []

    def __str__(self):
        return self.name


if __name__ == "__main__":

    frankfurt = City("Frankfurt")
    mannheim = City("Mannheim")
    karlsruhe = City("Karlsruhe")
    wurzburg = City("Wurzburg")
    stuttgart = City("Stuttgart")
    kassel = City("Kassel")
    munich = City("Munich")
    augsburg = City("Augsburg")
    erfurt = City("Erfurt")
    nurmberg = City("Nurmberg")

    frankfurt.adjacent = [mannheim, kassel, wurzburg]
    mannheim.adjacent = [karlsruhe, frankfurt]
    karlsruhe.adjacent = [augsburg, mannheim]
    augsburg.adjacent = [munich, karlsruhe]
    wurzburg.adjacent = [erfurt, nurmberg]
    nurmberg.adjacent = [stuttgart]
    munich.adjacent = [augsburg, kassel]
    kassel.adjacent = [frankfurt, munich]
    erfurt.adjacent = [wurzburg]
    stuttgart.adjacent = [nurmberg]

    graph = [
        erfurt,
        frankfurt,
        stuttgart,
        mannheim,
        karlsruhe,
        wurzburg,
        kassel,
        augsburg,
        nurmberg,
        munich,
    ]

    bfs(graph, frankfurt)