Return to Question

• 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)

• 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)

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
• 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)

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)
```

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