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[0]]
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[0]]
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. [1] 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[0]
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[0]
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