Breadth First Search (BFS) in Python

import queue


class BreadthFirstSearch:
    def __init__(self, graph):
        """
        graph: Graph represntation in the form of an adjecency list.
            E.g:  `B <- A -> C`, graph = { 'A' : ['B','C'], }
        """
        self._graph = graph

    def head(self):
        # NOTE: In Python 3.7.0 the insertion-order preservation nature of
        # dict objects has been declared to be an official part of the
        # Python language spec.*
        return next(iter(self._graph.keys()))

    def traverse(self):
        """Traverse all nodes in graph and print the followed path."""

        visited = set()  # Keeps track of visited nodes
        fifo = queue.Queue()  # First in First Out Queue
        log = []

        node = self.head()
        visited.add(node)
        fifo.put(node)

        while not fifo.empty():
            node = fifo.get()
            log.append(node)

            for neighbour in self._graph[node]:
                if neighbour not in visited:
                    visited.add(neighbour)
                    fifo.put(neighbour)

        return "Traverse graph: " + " ".join(log)

    def find_shortest_path(self, target):
        """Find shortest path to `target` node."""

        fifo = queue.Queue()
        fifo.put([self.head()])
        visited = set()

        while not fifo.empty():
            path = fifo.get()
            node = path[-1]  # last node on the path

            # BFS has the extremely useful property that if all edges in a
            # graph are unweighted (or the same weight), then the first time
            # a target node is visited is the shortest path to that node
            # from the head/source node.
            if node == target:
                return f"Shortest path to target: {path}"

            # check if the current node is already in the visited nodes set in
            # order not to recheck it
            elif node not in visited:
                # enumerate all adjacent nodes, construct a new path and push
                # it into the queue
                for current_neighbour in self._graph.get(node, []):
                    new_path = list(path)
                    new_path.append(current_neighbour)
                    fifo.put(new_path)

                visited.add(node)

        return "Target node is not reachable from head node"


#     A
#   +-^---+
#   B     |
# +-^-+   |
# D   E   C
#     ^-+-^
#       F
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

bfs = BreadthFirstSearch(graph)

print(bfs.traverse())
>> Travers: A B C D E F

print(bfs.find_shortest_path("F"))
>> Shortest path to target: ['A', 'C', 'F']