Problem

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

Solution

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