3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Could you include the output of your DFS and BFS algorithms using your example (parent 1, child 2, child 3) ? And perhaps also with child 2 having its own child 4. \$\endgroup\$ – dfhwze Jun 2 at 12:11
  • \$\begingroup\$ Thanks for the update in the question. Both your algorithms are in Pre-Order. \$\endgroup\$ – dfhwze Jun 2 at 12:34
  • \$\begingroup\$ Is this written for Python 2 or 3? \$\endgroup\$ – Mast Jun 2 at 12:46
  • \$\begingroup\$ Python 3. sorry \$\endgroup\$ – EML Jun 2 at 13:02
  • 1
    \$\begingroup\$ You talk about graphs and trees seemingly interchangeably. If your code works on graphs in general, then I'd rephrase the question to say that you are traversing graphs. \$\endgroup\$ – 200_success Jun 3 at 4:39
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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