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.