Breadth-first search(BFS) Implementation in Python 3 [closed]

I have implemented a BFS. Does this look like a proper implementation of BFS in Python 3? And if you think something needs to be improved, say it.

class Node(object):

    def __init__(self, name):
        self.name = name
        self.adjacencyList = []
        self.visited = False
        self.predecessor = None

class BreadthFirstSearch(object):

    def bfs(self, startNode):

        queue = []
        queue.append(startNode)
        startNode.visited = True

        # BFS -> queue      
        while queue:

            actualNode = queue.pop(0)
            print(actualNode.name)

            for n in actualNode.adjacencyList:
                if not n.visited:
                    n.visited = True
                    queue.append(n)

node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
node5 = Node("E")

node1.adjacencyList.append(node2)
node1.adjacencyList.append(node3)
node2.adjacencyList.append(node4)
node4.adjacencyList.append(node5)

bfs = BreadthFirstSearch()
bfs.bfs(node1)

There are a few PEP8 issues:

• In Python3, class definitions have been overhauled a bit, and one can simply do class Node: instead of class Node(object):.
• The spacing is a bit all over the place: there should be two blank lines between class definitions, and I find the spacing within def bfs(self, start_node) difficult.
• The naming convention is to be snake_cased.

To address this type of issues, have a look at flake8 or black

Node.visited is problematic.
First, if the node is in several trees, you may not visit it if it’s already been visited in another tree, or even in the same tree when doing a second search.

The fact that you have visited a node is part of the algorithm, and not so much a property of a Node.

With a few tweaks you can rely on queue only, or have a second list of visited:

visited = []
for node in current_node.adjacency_list:
   if not node in visited:
        visited.append(node)

The comment #BFS -> queue is not very telling.

Lastly, this is iterating through the tree, and not doing actual search. Where’s the exit condition? What’s returned? What should I get when searching for node4 from node1? node4 from node3? node3 from node2?

It’s not quite done…

collections.deque()

The documentation for collections.deque() says it is more efficient than a list when appending/popping elements. (Popping the 0th element from a list, may cause the rest of the list to be copied forward one space.) So use a deque instead of a list for the queue.

set()

Use a set() instead of a list() for the adjacent nodes. Also use a set for the visited nodes. This lets you do set difference to determine what nodes to add to the queue.

from collections import deque

def bfs(self, startNode):

    visited_set = set(startNode)
    queue = deque(visited_set)

    while queue:

        actual_node = queue.popleft()
        print(actual_node.name)

        unvisited_nodes = actual_node.adjacency_set - visited_set
        for node in unvisited_nodes:

            # here is where you test to see if `node` is the search target
            # and take some action if it is.

        # otherwise append all the unvisited nodes to the queue and continue searching
        queue.extend(unvisited)
        visited_set |= unvisited