Graph and Node classes with BFS and DFS functions

Question

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
 def add_node(self, val):
 newNode = Node(val)
 self.nodes.append(newNode)
 def add_edge(self, node1, node2):
 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()
graph.add_node(5)
graph.add_node(3)
graph.add_node(8)
graph.add_node(1)
graph.add_node(9)
graph.add_node(2)
graph.add_node(10)
# 2
# /
# 5 - 3 - 8 - 9 - 10
# \ /
# 1
graph.add_edge(graph.nodes[0], graph.nodes[1])
graph.add_edge(graph.nodes[0], graph.nodes[3])
graph.add_edge(graph.nodes[1], graph.nodes[2])
graph.add_edge(graph.nodes[0], graph.nodes[1])
graph.add_edge(graph.nodes[2], graph.nodes[3])
graph.add_edge(graph.nodes[2], graph.nodes[5])
graph.add_edge(graph.nodes[2], graph.nodes[4])
graph.add_edge(graph.nodes[4], graph.nodes[6])
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.

Answer 1

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
 def add_node(self, val):
 new_node = Node(val)
 self.nodes.append(new_node)
 def add_edge(self, node1, node2):
 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)
 visited.add(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)
 visited.add(nd)
 return result
graph = Graph()
graph.add_node(5)
graph.add_node(3)
graph.add_node(8)
graph.add_node(1)
graph.add_node(9)
graph.add_node(2)
graph.add_node(10)
# 2
# /
# 5 - 3 - 8 - 9 - 10
# \ /
# 1
graph.add_edge(graph.nodes[0], graph.nodes[1])
graph.add_edge(graph.nodes[0], graph.nodes[3])
graph.add_edge(graph.nodes[1], graph.nodes[2])
graph.add_edge(graph.nodes[0], graph.nodes[1])
graph.add_edge(graph.nodes[2], graph.nodes[3])
graph.add_edge(graph.nodes[2], graph.nodes[5])
graph.add_edge(graph.nodes[2], graph.nodes[4])
graph.add_edge(graph.nodes[4], graph.nodes[6])
dfs_result = graph.dfs()
bfs_result = graph.bfs()
print("DFS")
for i in range(len(dfs_result)):
 print(dfs_result[i].val)
print("BFS")
for i in range(len(bfs_result)):
 print(bfs_result[i].val)

Hope that helps.