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
- 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
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)
#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
It’s not quite done…
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() 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