A BFS and DFS implementation

Question

I believe this code prints both the DFS and BFS of a directed graph. As with some of my previous posts, this is mainly to share my code with other people working on a similar issue but I would also appreciate any feedback.

In the code I have written, DFS and BFS use a pre-order technique, as follows:

• DFS (Depth first search) starts with a given node and explores the first unexplored node it comes across before returning to itself again and exploring its remaining nodes (e.g: if the parent node 1 has 2 children 2, 3 the DFS method will explore 2 and its children nodes before exploring 3. It will print self before exploring its children (so 1->(2,3) will print 1,2,3))

• BFS (Breadth first search) works down a tree in a top-to-bottom manner (e.g: a graph with parent 1 and children 2, 3 will print level 1 first (1) then level 2 (2, 3) and then level 3 (the children of nodes 2 and 3). The level of a given node is determined by the highest level it could appear on (e.g: if 2 is a child of an item on level 1 and level 4, it would be printed as if it were a level 2 item)

from collections import defaultdict 

class Graph():
    def __init__(self):
        self.value = defaultdict(list)

    def addConnection(self, parent, child):
        self.value[parent].append(child)

    def DFS(self, start):
        visited = [start]
        stack = [start]
        print(start, end = " ")
        while stack:
            s = stack[-1]
            if any([item for item in self.value[s] if item not in visited]):
                for item in [item for item in self.value[s] if item not in visited]:
                        stack.append(item)
                        visited.append(item)
                        print(item, end= " ")
                        break
            else:
                stack.pop()

    def BFS(self, start):
        visited = [start]
        queue = [start]
        while queue:
            x = queue.pop(0)
            print(x, end= " ")
            for item in self.value[x]:
                if item not in visited:
                    queue.append(item)
                    visited.append(item)

#Build the graph
g=Graph()
g.addConnection(1,4)
g.addConnection(1,2)
g.addConnection(2,3)
g.addConnection(2,6)
g.addConnection(4,5)
g.addConnection(4,7)
g.addConnection(7,96)

#Explore the graph
g.DFS(1)
print("\n")
g.BFS(1)

Output is

DFS: 1 4 5 7 96 2 3 6
BFS: 1 4 2 5 7 3 6 96

Adding a (2,4) node gives

DFS: 1 4 5 7 96 2 3 6
BFS: 1 4 2 5 7 3 6 96

Answer 1

Clarification (OK)

After update of your question, it has gotten clear that:

• you work on a DAG, which includes a Tree
• both your strategies DFS and BFS are in Pre-Order

---

=> original answer requesting clarification from the OP

Review Definitions

Before being able to review your code, I would like to review your definitions. Perhaps you should clarify your algorithm with examples.

I believe this code prints both the DFS and BFS of a directed graph.

How do you decide the breadth level of a node when it has multiple parents? Or would you only work with Tree instead of DAG?

As a reminder of the difference:

DFS (Depth first search) starts with a given node and explores the first unexplored node it comes across before returning to itself again and exploring its remaining nodes (e.g: if the parent node 1 has 2 children 2, 3 the DFS method will explore 2 and its children nodes before exploring 3

Because you say to explore remaining nodes before returning to self, you are not very clear whether the order is A or B.

• (A) 1 -> 2 -> 3
• (B) 2 -> 3 -> 1

BFS (Breadth first search) works down a tree in a top-to-bottom manner (e.g: a graph with parent 1 and children 2, 3 will print level 1 first (1) then level 2 (2, 3) and then level 3 (the children of nodes 2 and 3)

The order is independant of search strategy (DFS/BFS). BFS can be both top-to-bottom or bottom-to-top.

---

Terminology

• DFS: process each child completely before processing the next child
• BFS: process each level across childs before processing the next level
• Pre-Order: process self before rest of tree
• Post-Order: process rest of tree before self

In your example of parent 1 having child 2 and child 3:

• DFS Pre-Order: 1 -> 2 -> 3
• DFS Post-Order: 2 -> 3 -> 1
• BFS Pre-Order: 1 -> 2 -> 3
• BFS Post-Order: 2 -> 3 -> 1

Suppose 2 would have its own child 4:

• DFS Pre-Order: 1 -> 2 -> 4 -> 3
• DFS Post-Order: 4 -> 2 -> 3 -> 1
• BFS Pre-Order: 1 -> 2 -> 3 -> 4
• BFS Post-Order: 4 -> 2 -> 3 -> 1

You could even add a third dimension direction in which case we distinguish left-to-right and right-to-left.