# Graph and Node classes with BFS and DFS functions

I've created a Node class and a Graph class

class Node:
def __init__(self, val):
self.val = val
self.edges = []

class Graph:
def __init__(self, nodes=[]):
self.nodes = nodes

newNode = Node(val)
self.nodes.append(newNode)

node1.edges.append(node2)
node2.edges.append(node1)


I have also added functions to the Graph class for performing breadth first search and depth first search on a given graph.

def bfs(self):
if self.nodes is None:
return []
visited, toVisit = [], [self.nodes]
while toVisit:
node = toVisit.pop()
visited.append(node)
print(node.val)
for nd in node.edges:
if nd not in visited and nd not in toVisit:
toVisit.insert(0,nd)
return visited

def dfs(self):
if self.nodes is None:
return []
visited, toVisit = [], [self.nodes]
while toVisit:
node = toVisit.pop()
visited.append(node)
print(node.val)
for nd in node.edges:
if nd not in visited and nd not in toVisit:
toVisit.append(nd)
return visited


Here is an example implementation

graph = Graph()

#            2
#           /
# 5 - 3 - 8 -  9 - 10
#  \    /
#     1

graph.dfs()
graph.bfs()


The depth first search returns 5,1,8,9,10,2,3

The breadth first search returns 5,3,1,8,2,9,10

From what I can tell, this is a correct implementation. However, I'm curious if there are more efficient ways to do some of these things. Or maybe ways that make more logical sense. For example, am I storing the edge list in a reasonable way? Is this generic enough that it could easily be extended to work with directed vs undirected graphs? Any feedback would be much appreciated.

## Algorithm

Both your BFS and DFS run in time $\mathcal{O}(EV)$ due to this:

if nd not in visited and nd not in toVisit:


Since toVisit is a list, finding whether nd not in toVisit will have to iterate over all elements in that list. Since the above if will be iterated around $\Theta(E)$ times, and len(toVisit) $\leq |V|$, the total work may be as large as $\mathcal{O}(EV)$.

What you could do above in order to

if nd not in visited and nd not in toVisit:


in constant time, is to add a set that stores the graph nodes already reached by the search. In order for that to happen, you have to add a couple of special methods to your Node class:

class Node:
def __init__(self, val):
self.val = val
self.edges = []

# Do this and other represent the same node?
def __eq__(self, other):
return self.val == other.val

# Used for finding the collision chain for this node.
def __hash__(self):
return self.val


Note that set() is implemented as a hash table that runs both insertion and query operations in constant time.

Also, I strongly suggest that you do not print to standard output from an algorithm. Instead, arrange an output from the algorithm that may be printed.

Also, taking a look at bfs, there is an improvement opportunity as well: you use a list for representing the search frontier queue. Appending is efficient, yet removing the head node of that "queue" runs in linear time. Instead, use collections.deque(); it allows both pops and pushes in constant time.  https://wiki.python.org/moin/TimeComplexity

## Naming

Python suggest new_node instead of newNode. Same applies to toVisit.

## Misc

The test if self.nodes is None: may be rewritten more succintly:

if not self.nodes:


The above will deal with self.nodes == None and len(self.nodes) == 0.

## Summa summarum

All in all, I had this in mind:

from collections import deque

class Node:
def __init__(self, val):
self.val = val
self.edges = []

def __eq__(self, other):
return self.val == other.val

def __hash__(self):
return self.val

class Graph:
def __init__(self, nodes=[]):
self.nodes = nodes

new_node = Node(val)
self.nodes.append(new_node)

node1.edges.append(node2)
node2.edges.append(node1)

def bfs(self):
if not self.nodes:
return []
start = self.nodes
visited, queue, result = set([start]), deque([start]), []
while queue:
node = queue.popleft()
result.append(node)
for nd in node.edges:
if nd not in visited:
queue.append(nd)
return result

def dfs(self):
if not self.nodes:
return []
start = self.nodes
visited, stack, result = set([start]), [start], []
while stack:
node = stack.pop()
result.append(node)
for nd in node.edges:
if nd not in visited:
stack.append(nd)
return result

graph = Graph()

#            2
#           /
# 5 - 3 - 8 -  9 - 10
#  \    /
#     1