6
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.