Breadth First Search Python code to Depth First Search

Question

I have written some code that conducts a BFS when a graph is defined. I now need to Edit the code to do a DFS, does anyone know what i need to change to complete this?

This is the BFS code i have now:

class MyQUEUE: # Just an implementation of a queue.
def __init__(self): # Initialises the queue to an empty queue.
    self.holder = []

def enqueue(self,val):
# Appends item val onto the end of the queue.
    self.holder.append(val)

def dequeue(self):
    # Pops the head off the queue and returns it value.
    val = None
    try:
        val = self.holder[0]
        if len(self.holder) == 1:
            self.holder = []
        else:
            self.holder = self.holder[1:]
    except:
            pass
    return val

def IsEmpty(self):
    # Returns True if the queue is empty.
    result = False
    if len(self.holder) == 0:
        result = True
return result


def BFS(graph,start,end):
# Traverses the graph using a Breadth First Search starting
# from the start node with end being the goal node. Uses a
# queue to store the nodes that are current leaves at the
# fringe of the search.

q = MyQUEUE() # make an empty queue first
q.enqueue([start]) # add the start node onto the queue
while q.IsEmpty() == False:
    path = q.dequeue()
    last_node = path[len(path)-1]
    print (path)
    if last_node == end:
        print ("VALID_PATH : ", path)
    for link_node in graph[last_node]:
        if link_node not in path:
            new_path = []
            new_path = path + [link_node]
            q.enqueue(new_path)

Does this answer your question? Convert BFS code for a graph into a DFS code — GPhilo
– GPhilo, Commented Mar 9, 2020 at 11:54

Nir Alfasi · Accepted Answer · 2020-03-09 12:16:03Z

4

Instead of append - insert at the beginning:

modify:

self.holder.append(val)

to:

self.holder.insert(0, val)

Explanation

While BFS "pills" the neighbors "layer by layer" a DFS goes "all the way to the bottom" and back. By changing the order we iterate the neighbors (recursively) we are, in fact, modifying the BFS into DFS.

UPDATE

As Kaya commented below, if we care about performance we should use append/pop instead of insert because insert takes O(n) while append/pop are O(1)

edited Mar 9, 2020 at 12:16

answered Mar 9, 2020 at 11:57

Nir Alfasi

53.6k11 gold badges93 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

kaya3 Over a year ago

If you want to use a list as a stack, you should use append(...) and pop() instead of insert(0, ...) and slicing, because the former take O(1) time and the latter take O(n) time.

Nir Alfasi Over a year ago

@kaya3 you're right, that's definitely a better option, answer updated!

Collectives™ on Stack Overflow

Breadth First Search Python code to Depth First Search

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related